poj 3641 Pseudoprime numbers

Pseudoprime numbers

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 7000		Accepted: 2855

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

 1 #include<cstdio>
 2 #include<cmath>
 3 #include<cstring>
 4 #include<iostream>
 5 using namespace std;
 6 #define max 1000000000
 7 typedef long long ll;
 8 bool isprime(int n){//判断素数，该题max过大，不适合用打表法
 9     if(n==0||n==1){
10         return false;
11     }
12     if(n==2){
13         return true;
14     }
15     if(n%2==0)
16         return false;
17     int i=3,half=sqrt(n*1.0);
18     for(;i<=half;i+=2){
19         if(n%i==0){
20             return false;
21         }
22     }
23     return true;
24 }
25 ll work(ll a,ll b,ll k){//a^b mod k  快速幂模板
26     if(a==0){
27         return 0;
28     }
29     if(b==0){
30         return 1;
31     }
32     ll x=a%k,ans=1;
33     for(;b>0;b/=2){
34         if(b%2){
35             ans=(ans*x)%k;//这歩一定是会最后到达 
36         }
37         x=x*x%k;
38     }
39     return ans;
40 }
41 int main()
42 {
43     int p,a;
44     while(cin>>p>>a&&p&&a){
45          //cout<<isprime(p)<<endl;
46          if(!isprime(p)&&(work(a,p,p)==a%p)){//注意素数判断
47              cout<<"yes"<<endl;
48          }        
49          else{
50              cout<<"no"<<endl;
51          }
52     }
53     return 0;
54 }