PKU 3641 Pseudoprime numbers
http://poj.org/problem?id=3641
二つの整数p,aが与えられる。
ここでpが素数でなく、a^p≡a (mod p)となっているかを判定しろというような問題。
素数判定と繰り返し二乗法。
ll modPow(int a,int p,int MOD){ ll ret=1; ll base=a; while(p){ if(p&1)ret=ret*base%MOD; base=base*base%MOD; p/=2; } return ret; } bool isPrime(ll p){ if(p==1)return false; for(ll i=2;i*i<=p;++i) if(p%i==0)return false; return true; } main(){ ll p,a; while(cin>>p>>a,p) puts(!isPrime(p) && modPow(a,p,p)==a?"yes":"no"); }