2011年12月17日 星期六

11287 - Pseudoprime Numbers


費馬定理表示對於所有的質數 p 及任何大於1的整數 a,存在 a^p == a(mod p)的關係,也就是說,將 a 的 p 次方除以 p 所得到的餘數為 a。對於某些非質數的 p 而言,存在一些滿足此關係式的 a 值,此非質數的 p 稱為"base-a pseudoprime"。

給定 2 < p <= 1,000,000,000且1 < a < p,請判斷 p 是否為"base-a pseudoprime",是請輸出"yes",否則請輸 出"no"。

每組測試資料給定兩個整數分別表示 p 與 a ,當 p = a = 0 表示測試資料結束。

Sample Input

3 2
10 3
341 2
341 3
1105 2
1105 3
0 0

Output for Sample Input

no
no
yes
no
yes
yes

原文出處

沒有留言:

張貼留言