Top > 3641 Pseudoprime numbers


3641 Pseudoprime numbers

Last-modified: 2010-04-08 (木) 21:57:43

原文


時間制限:1000ミリ秒
メモリ制限:65536KB

問題 Edit

 フェルマーの小定理は、すべての素数pと、pの倍数でない整数a (a > 1)に関して、a^p ≡ a (mod p) ということを示している。この式は、aのp乗をpで割った余りがaであることを表している。いくつかの(多くはない)素数でない数も、この式をいくつかのaに関して満たすことがある(これは底aの擬素数として知られている)。(そして、カーマイケル数として知られる数は、すべての底aに対して擬素数である。)

入力 Edit

 入力は複数のテストケースを含み、最後の行は"0 0"である。各テストケースは、pとaを含む行からなる。

出力 Edit

 それぞれのテストケースについて、pが底aの擬素数なら"yes"、そうでなければ"no"と出力しなさい。

入力の例 Edit

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

出力の例 Edit

no
no
yes
no
yes
yes

出典 Edit

Waterloo Local Contest, 2007.9.23