回分類題庫
h132: B.寧寧數貓咪
關鍵字: NPSC 2014 高中組初賽

測資點 : 2 | Time Limit : 10000 ms | Memory Limit : 128000 KB
Accepted : 45 Times / 37 Users | Submit : 218 Times / 52 Users | Accepted rate : 71%
題目加入時間 : 2015-11-10 13:32

Content: 简体中文

住在喵星上的寧寧是個十足的貓咪愛好者,為了能夠每天環繞在貓咪之中,她在家裡養了非常多的貓咪。由於貓咪的數量龐大,縱使飼料批發商已經以非常低廉的價錢賣飼料給寧寧了,貓咪飼料的開銷仍依然龐大。為了避免浪費太多錢,寧寧每隔一段時間便會統計究竟有幾隻貓咪在她家中,以控制飼料的量。

然而,隨著貓口膨脹,寧寧漸漸無法計算究竟有幾隻貓咪在她家中。為此,寧寧發明了一種新方法來計算貓咪的數量,稱之為「寧寧點貓」。寧寧點貓的方法很簡單。寧寧首先選擇 N 相異的質數 P1, P2, P3, . . . , PN 。接著寧寧會對貓咪們下 N 次指示,第 i 次時寧寧會要求貓咪們每 Pi 隻組成一團,最後落單找不到組的貓咪便來找寧寧。

如此經過 N 次的指示之後,寧寧便能知道貓咪的數量除以這些質數的餘數,並可以逆推出貓咪的數量了!當然,不論質數怎麼選,可能的貓咪數量依然會有無限種,但寧寧相信貓咪的數量一定是這所有可能中最少的那個!

發明了這個方法之後,寧寧便迫不及待的對貓咪們下了指示,但她很快的就發現了一個問題:她不知道該怎麼逆推出貓咪的數量!由於明天就要買飼料了,寧寧沒時間從頭數過,她找上傳說中數學非常好的你。究竟,你能不能幫助寧寧算出貓咪的數量呢? 

Input:

輸入的第一行有一個正整數 T 代表測試資料的筆數,接下來的每一行代表一筆測試資料。

每一筆測試資料的開頭有一個正整數 N 代表寧寧選了幾個質數。接下來跟著 2N 個整數,奇數項是寧寧所選的質數 Pi,而其對應的偶數項 Ri 便是最後來找寧寧的貓咪數量。

Output:

對於每一筆測試資料,請輸出貓咪的數量到底是多少。

如果貓咪的數量大於等於 955049953 隻,請輸出 −1 來告訴寧寧該少養些貓咪了。

Sample Input:help

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

Sample Output :

4
1
-1

Hint :

範例說明: 

第三筆測試資料中,貓咪的數量為 955049954 ,故必須輸出 −1 。

Author :

NPSC 2014 高中組初賽 (管理員:sagit)

  Solve it!   Status Forum