当前位置: 代码迷 >> 综合 >> HDU 1905 Pseudoprime numbers(快速幂)
  详细解决方案

HDU 1905 Pseudoprime numbers(快速幂)

热度:96   发布时间:2023-11-06 18:26:17.0

题意:

a的p次方p取模等于a,且p不是素数,就输出yes;

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#define ll long long
using namespace std;
ll powermod(ll a,ll b,ll c){ll ans=1;a = a % c;while(b>0){if(b%2) ans = (ans * a) %c;b = b/2;a = (a * a)%c;}return ans;	
} 
bool jud(ll x){ll te = sqrt(x);for(int i =2 ;i <= te; i++)if(!(x % i)) return 1;//x不是素数返回true return 0;
}
int main(){ll p,a; while(scanf("%I64d%I64d",&p,&a)){if(p == 0&&a == 0) break;ll te = powermod(a, p, p);if(te == a && jud(p)) puts("yes");else puts("no");}return 0;
}