Pseudoprime numbers(POJ-3641)(快速冪）
來源：程序員人生 發布時間：2015-05-22 08:38:28 閱讀次數：3412次
快速冪+素數判斷
p必須不是素數。
#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;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
