回分類題庫
d033: 2008 程式達人 G - 破解終極戰士(Predator)的密碼
出處:

Difficulity : 1
Accepted : 56 Times | Submit :102 Times | Clicks : 2002
Accepted : 43 Users | Submit : 44 Users | Accepted rate : 98%
Time Limit :2001 ms | Memory Limit : 32001 KBytes
題目加入時間 : 2008-10-10 10:26

Content :

政治大學的諸君

軍情局攔截到了一系列由終極戰士(predator)所發出的密文。他們正密謀於某天的某一時刻大舉侵襲地球。若能及時破解攔截到的密碼,就能預防此災難的發生。很幸運的,終極戰士所使用的密碼並不終極。軍情局已發現了他們的密碼系統的規則。終極戰士是利用 Dirichlet 等差級數定理來產生某個質數,並利用此質數來加密訊息(明文)。

Dirichlet 級數定理是說,給定 a 與 d 兩個互質的正整數,則等差級數 a, a+d, a+2d, a+3d, a+4d, …, a+id, …中包含有無限多個質數。舉例來說,如果a=2, d=3, 則等差級數 2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 41, 44, 47, 50, 53, 56, 59, 62, 65, 68, 71, 74, 77, 80, 83, 86, 89, 92, 95, 98, … 中,包含無限多個質數 2, 5, 11, 17, 23, 29, 41, 47, 53, 59, 71, 83, 89, …

只要知道其中某個質數,就可破解攔截到的密文。因此,諸君的任務就是,對於給定的 a, d, n,找到由 a, d 組成的等差級數中的質數集合中的第 n 個質數,並將結果回報給軍情局。舉例來說,2, 3, 5的結果為 23。2, 3, 8的結果為 47。

這是一個非常危險的任務。各位在任務期間產生的疲勞,頭暈目眩或混亂等等行為,皆源於終極戰士的電波干擾,但本局將採取一切不介入的原則。照往例,無論成功或失敗,軍情局都將會否認此任務的存在。此任務並將於 5 小時後自動失效。祝各位成功。

Input :

輸入檔由多列組成,每一列都有三個數字,依序代表 a, d, 以及 n。數字與數字之間以一個空白間隔。a, d 兩數互質。a ≤ 9000, d ≤ 350, 且n ≤ 210。

輸入檔的最後一列以 0 0 0 三個 0 表示測試案例的結尾(0 與 0 之間以一個空白間隔)。

 

Output :

每一列為一個整數,代表由 a, d 組成的等差級數中的質數集合中的第 n 個質數。

Sample Input :

1 1 1
253 50 85
307 24 79
331 221 177
269 58 102
367 186 151
0 0 0

Sample Output :

2
14503
5107
412717
25673
92809

Hint :

解題率:8/19

Author :

(管理員:MrWrongAnswer)

  Solve it!   Status Forum (3)

C++
C
JAVA
6910. Dlackty (14 ms , 354KB)
6889. Tc (20 ms , 346KB)
46277. ji8g2mu (26 ms , 226KB)
20844. liouzhou_101 (28 ms , 1216KB)
3240. deepdish (29 ms , 426KB)
6958. s95703049 (8 ms , 240KB)
6959. s95703049 (9 ms , 242KB)
55092. ag100 (16 ms , 1537KB)
6957. s95703049 (16 ms , 260KB)
2010. taop (16 ms , 244KB)
56392. nwgs524513cja (148 ms , 1410KB)

執行時間會受很多因素影響因此僅供參考,主機等級請看這裡