题意:
有多组数据,对于每组数据,给出 p 和 a ,如果 p 是质数或者 a^p \mod p ≠ a,输出no
,否则输出yes
。
此题就是判断质数+快速幂板子
快速幂如果不会可以看看这个[链接登录后可见]
根据题意来就行了。
具体注释见代码
code:
#include<bits/stdc++.h>
typedef unsigned long long ull;
using namespace std;
ull n,cnt,m;
bool p(ull x){//不开longlong见祖宗
if(x==1) return false;
for(ull i=2;i*i<=x;i++) if(x%i==0) return false;//只要判断到i*i<=x即可
return true;
} //判断质数
ull ksm(ull b,ull p){//快速幂模板
ull k=p;//模数就是p
ull x=1;//存答案
//不开longlong见祖宗!!
while(p){
if(p%2==0){
p/=2;
b=b*b%k;
}else{
p/=2;
x*=b;
x%=k;
b=b*b%k;
}
}//过程
return x;
}
int main(){
ull x,y;//不开longlong见祖宗!!!
while(cin>>x>>y&&(x!=0&&y!=0)){//x=0&&y=0时结束
if(!p(x)||ksm(y,x)==y) cout<<"yes\n";//根据题意写
else cout<<"no\n";
}
return 0;//结束/qq
}
最后,不开longlong见祖宗!(我被坑了TvT)