回分類題庫
h113: F.史萊姆森林
關鍵字: NPSC 2012 高中組決賽

測資點 : 2 | Time Limit : 10000 ms | Memory Limit : 512000 KB
Accepted : 12 Times / 7 Users | Submit : 75 Times / 23 Users | Accepted rate : 30%
題目加入時間 : 2013-11-07 13:29

Content: 简体中文

傳說中,在 NPSC 大陸的某片森林深處住著一群史萊姆。這群史萊姆非常好戰,每當有兩隻史萊姆相遇時,他們總會打 1018 回合,或是打到有其中一方戰死才肯罷休。身為一個史萊姆生態研究員,蚯蚓決定前往這片森林研究這些特別的史萊姆。

在觀察後,蚯蚓發現一個特別的現象:兩隻史萊姆打架時,常常分不出勝負,而且輸贏跟兩隻史萊姆的大小似乎沒什麼關係!在更進一步研究後,蚯蚓發現這似乎與史萊姆特殊的打架方式有關。

假設有兩隻大小為 a, b (a>b) 的史萊姆在打架,則大小為 b (比較小) 的那隻會發動攻擊,並且在攻擊完後將 a 的一部分吸收。這一回合後兩隻史萊姆的大小會變為 a−b, b+b,再由比較小的那隻史萊姆再度發動攻擊,以此類推。若當兩隻史萊姆的大小變得一樣時,兩方會發動最後的攻擊,而速度較快的一方就會擊敗對方、將對方完全吸收,而若在打了 1018 回合後都沒有一方戰敗,兩隻史萊姆就會休戰。

蚯蚓很好奇,在眾多的史萊姆中,究竟有幾對史萊姆相遇時是會分出勝負的? 

Input:

輸入檔的第一行有一個正整數 T (T<=10),表示接下來總共有幾筆測試資料。

每一筆測試資料的開頭有一個正整數 N (N<=105),代表森林中有幾隻史萊姆。接下來有 N 個正整數 Si 代表該隻史萊姆的大小,史萊姆的大小不會超過500000。 

Output:

對每筆測試資料請輸出一個整數,代表有幾對史萊姆相遇時是會分出勝負的。

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
2
3 5 1 4
4 1 2 3 4

Sample Output :

0
1

Hint :

範例說明:

第二筆測試資料中,只有 (1,3) 能分出勝負。 

Author :

NPSC 2012 高中組決賽 (管理員:sagit)

  Solve it!   Status Forum