本文共 1603 字，大约阅读时间需要 5 分钟。

Description

Fermat's theorem states that for any prime number p and for any integer a > 1, ap = 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 ≤ 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

3 210 3341 2341 31105 21105 30 0

Sample Output

nonoyesnoyesyes

很基础的一道快速幂取模的题目....

只需要判断a^p%p与a%p两个结果是否相等和判断p是否为素数即可...

代码如下：

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;typedef long long ll;ll p,a;ll Fast (ll a,ll b){    ll sum=1,mod=b;    while (b>0)    {        if(b&1)        {            sum=sum*a%mod;        }        b>>=1;        a=a*a%mod;    }    return sum;}bool Is_pri (ll x){    if(x==1)        return false;    for (int i=2;i<=sqrt(x);i++)           if(x%i==0)              return false;    return true;}int main(){    while (scanf("%lld%lld",&p,&a)!=EOF&&(p||a))    {        ll mod1=a%p;        ll mod2=Fast(a,p);        if(mod2==mod1)        {            if(Is_pri(p))                printf("no\n");            else                printf("yes\n");        }        else            printf("no\n");    }    return 0;}
       
      
     
    
   

转载地址：http://paaen.baihongyu.com/