模运算。。

Pseudoprime numbers

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 876    Accepted Submission(s): 358

Problem 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 pth 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 ≤ 1,000,000,000 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

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

 

 

Sample Output

no no yes no yes yes

1 #include
        
          2 #include
         
           3 #include
          
            4 __int64 sushu(__int64 a) 5 { 6     __int64 i; 7     if(a%2 == 0) 8     return 0; 9     for(i = 3; i < sqrt(a); i+=2)10     {11         if(a%i == 0)12         return 0;13     }14     return 1;15 }16 __int64 ab(__int64 a, __int64 p, __int64 x)//模运算公式17 {18     __int64 s;19     if(p==0)20     return 1;21     if(p==1)22     return a%x;23     if(p == 2)24     return (a*a)%x;25     s=ab(a,p/2,x);26     if(p%2 == 0)27     return (s*s)%x;28     else29     return (((s*s)%x)*a)%x;30 31 }32 int main()33 {34     __int64 p, a, x;35     while(scanf("%I64d %I64d",&p,&a) != EOF)36     {37         if(p==0&&a==0)break;38         if(sushu(p)==1)39         printf("no\n");40         else41         {42             x = ab(a,p,p);43             if(x==a)44             printf("yes\n");45             else46             printf("no\n");47         }48     }49     return 0;50 }