HDU 3641 Pseudoprime numbers（快速幂）

Pseudoprime numbers

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 11336		Accepted: 4891

Description

Fermat's theorem states that for any prime number p and for any integer a > 1, a^p = a (mod p). That is, if we raise a to the p^th power and divide by p, the remainder is a. Some (but not very many) non-prime values of p, known as base-a pseudoprimes, have this property for some a. (And some, known as Carmichael Numbers, are base-a pseudoprimes for all a.)

Given 2 < p ≤ 1000000000 and 1 < a < p, determine whether or not p is a base-a pseudoprime.

Input

Input contains several test cases followed by a line containing "0 0". Each test case consists of a line containing p and a.

Output

For each test case, output "yes" if p is a base-a pseudoprime; otherwise output "no".

Sample Input

Sample Output

no
no
yes
no
yes
yes

Source

Waterloo Local Contest, 2007.9.23

题意：p不是素数，且a^p对p取模等于a，输出yes，其他的输出no。

题解：判断p是否是素数那部分直接蛮力求就好。

 1 #include <iostream>
 2 using namespace std;
 3 typedef long long ll;
 4 bool is_prime(ll x)
 5 {
 6     int i;
 7     if (x == 2) return 1;
 8     if (x == 1) return 0;
 9     for (i = 2; i*i < x; i++)
10     {
11         if (x %i == 0)
12             return 0;
13     }
14     return 1;
15 }
16 int main()
17 {
18     ll a, p;
19     while (cin >> p>>a)//p=n
20     {
21         if (a == 0 && p == 0) break;
22         if (is_prime(p))
23         {
24             cout << "no" << endl;
25             continue;
26         }
27         ll ans = 1;
28         ll k = p;
29         ll x = a;
30         while (p > 0)
31         {
32             if (p & 1) ans = (ans * a)%k;
33             a = (a * a)%k;
34             p >>= 1;
35 
36         }
37         if (ans%k == x) cout << "yes" << endl;
38         else cout << "no" << endl;
39     }
40     return 0;
41 }