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

判断a ^ p = a % p   (p是合数)      true?yes：no

#include
   
    #include
    
     typedef long long  LL;bool is_prime(LL p){    if(p == 1|| p == 2) return true;    for(LL i = 2;i <= sqrt(p);i++)        if(p%i==0) return false;    return true;}LL fast_pow(LL x,LL p,LL MOD)//快速幂{    LL res = 1;    while(p)    {        if(p&1) res = (res * x) % MOD;        x = (x*x)%MOD;        p>>=1;    }    return res;}int main(){    LL a,p;    while(scanf("%lld%lld",&p,&a),p|a)    {        if(is_prime(p)) {printf("no\n");continue;}        LL r = fast_pow(a,p,p);        if(r == a%p) printf("yes\n");//此处不能用r == 1作为判断        else printf("no\n");    }}
    
   

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