Pseudoprime numbers(POJ-3641)(快速幂）

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<queue> #include<vector> #include<map> using namespace std; typedef long long ll; ll a,p; ll mod_pow(ll x,ll n,ll mod) { ll res = 1; while(n>0) { if(n & 1) res = (res * x) % mod; x = (x * x) % mod; n >>= 1; } return res; } bool is_prime(int a) { for(int i=2;i*i<=a;i++) if(a%i==0) return false; return true; } int main() { while(~scanf("%lld%lld",&p,&a)) { if(a==0&&p==0) return 0; long long v = mod_pow(a,p,p); if(v==a%p&&!is_prime(p)) printf("yes "); else printf("no "); } return 0; }