判断p是否为素数且(a^p)%p是否等于a即可
#include <iostream> using namespace std; #define debug freopen("in.txt","r",stdin),freopen("out.txt","w",stdout); #define ios ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); //#define PI acos(-1) typedef long long ll; //const int maxn = 1e9; int isprime(int n) { for(int i=2;i*i<=n;i++) if(n%i == 0) return 0; return 1; } ll mypow(ll x, ll& y, ll mod) { ll ans = 1; while (y) { if (y & 1) ans = (x * ans) % mod; x = (x * x) % mod; y >>= 1; } return ans; } int main() { //debug; ios; ll a, p; while (cin >> p >> a) { if (a == 0 || p == 0) break; if(isprime(p)) cout << "no" << '\n'; else if (mypow(a, p, p) == a) cout << "yes" << '\n'; else cout << "no" << '\n'; } return 0; }