题目大意
判断一个数是否是伪素数
题解
赤果果的快速幂取模。。。。
代码：
#include<iostream>
#include<cmath>
using namespace std;
#define LL long long
LL mul_mod(LL a,LL b,int n)
{
return a*b%n;
}
LL pow_mod(LL a,LL p,LL n)
{
if(p==0) return 1;
LL ans=pow_mod(a,p/2,n);
ans=ans*ans%n;
if(p%2==1) ans=ans*a%n;
return ans;
}
bool prime(LL n)
{
if(n<2) return false;
for(int i=2;i*i<n;i++)
if(n%i==0) return false;
return true;
}
int main()
{
int a,p;
while(cin>>p>>a&&p+a)
{
if(a%p==pow_mod(a,p,p))
{
if(!prime(p))
cout<<"yes"<<endl;
else
cout<<"no"<<endl;
}
else
cout<<"no"<<endl;
}
return 0;
}