根据费马定理 当p为素数 a>1时 有(a^p)%p==a%p
有少部分非素数 对a也能满足该公式 这些素数称为a的伪素数 问给定的p和a p是不是a的伪素数
快速幂问题
注意p<10^9 可能爆掉int
#include<iostream> #include<cstdlib> #include<cstdio> #include<string> #include<vector> #include<deque> #include<queue> #include<algorithm> #include<set> #include<map> #include<stack> #include<ctime> #include<cmath> #include<list> #include<cstring> //#include<memory.h> using namespace std; #define ll long long #define ull unsigned long long #define pii pair<int,int> #define INF 1000000007 #define pll pair<ll,ll> #define pid pair<int,double> #define sci(a) scanf("%d",&a) #define scd(a) scanf("%lf",&a) #define scs(a) scanf("%s",a) #define pri(a) printf("%d\n",a); #define prd4(a) printf("%.4lf\n",a); #define prs(a) printf("%s\n",a); bool isprime(int n){//判断n是否为素数 int end=sqrt(n+1); for(int i=2;i<=end;++i) if(n%i==0) return false; return true; } int fast_pow(int a,int n,int mod){//快速幂 int res=1; while(n){ if(n&1) res=((ll)res*a)%mod;//强制类型转换 防止爆掉 a=((ll)a*a)%mod; n>>=1; } return res; } int main(){ //freopen("/home/lu/文档/r.txt","r",stdin); //freopen("/home/lu/文档/w.txt","w",stdout); int p,a; while(scanf("%d%d",&p,&a),a+p) prs((!isprime(p)&&fast_pow(a,p,p)==a%p)?"yes":"no"); return 0; }