本文共 1555 字，大约阅读时间需要 5 分钟。
常用的判定素数的函数
bool is_prime(int n){ if (n < 2){ return false; } int i; for (i = 2; i*i <= n; i++){ if (n%i == 0){ return false; } } return true;
}
快速幂的模板
long long modexp(long long a, long long b, int mod){ long long res=1; while(b>0) { a=a%mod;(有时候n的值太大了会超出long long的储存，所以要先取余) if(b&1)//&位运算：判断二进制最后一位是0还是1，&的运算规则为前后都是1的时候才是1； res=res*a%mod; b=b>>1;//相当于除以2； a=a*a%mod; } return res;}
接下来就是hd 3641
#include <cstdio>#include <iostream>#include <cstring>#include <algorithm>using namespace std;typedef long long ll;ll quickpow(ll a,ll b,ll c)//a的b次方对c取余{ ll ans=1; a=a%c; while(b) { if(b%2==1) ans=ans*a%c; b>>=1;// b=b/2; a=a*a%c; } return ans;}int main(){ int flag; ll a,p; while(~scanf("%lld%lld",&p,&a)&&(a||p)) { flag=0; for(int i=2;i*i<p;++i) { if(p%i==0) { flag=1; break; } } if(!flag) cout<<"no"<<endl; else { ll tem=quickpow(a,p,p); if(tem==a) cout<<"yes"<<endl; else cout<<"no"<<endl; } } return 0;
}
-------------------------
#include <iostream> using namespace std; int prime(long long a) { int i; if(a == 2) return 1; for(i = 2; i*i<=a; i++) if(a%i == 0) return 0; return 1; } long long mod(long long a,long long b,long long c) { long long ans = 1; a=a%c; while(b>0) { if(b%2==1) ans=(ans*a)%c; b=b/2; a=(a*a)%c; } return ans; } int main() { long long a,p; while(cin >> p >> a) { if(p==0 && a==0) break; long long ans; if(prime(p)) cout << "no" << endl; else { ans = mod(a,p,p); if(ans == a) cout << "yes" << endl; else cout << "no" << endl; } } return 0;
}
http://www.hankcs.com/program/cpp/poj-3641-pseudoprime-numbers.html
快速幂的一点讲解
转载地址：https://blog.csdn.net/weixin_38960774/article/details/79387329 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！
发表评论
最新留言
关于作者
