题意：//给一个p 和一个a，如果这个
//p 本身就是一个素数，就输出no，如果不是素数，那么计算 ( a ^ p) % p 如果结果等于a
那么输出yes 否则输出no
zsd:用__int64的时候一定要注意__int64与别的数转化的时候会出错误 所以一定要都是__int64位
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41 |
//给一个p 和一个a，如果这个//p 本身就是一个素数，就输出no，如果不是素数，那么计算 ( a ^ p) % p 如果结果等于a 那么输出yes 否则输出no#include<iostream>#include<cmath>using
namespace std;bool
isprime(int
x){ for(int
i=2;i<=(int)sqrt(x*1.0)+1;i++) if(x%i==0) return
false; return
true;}bool
fun(__int64
x,__int64
e,__int64
p){ __int64
a=x; __int64
base=x; __int64
sum=1; while(e>0) { if(e&1) sum=(sum*base)%p; e/=2; base=(base*base)%p; } if(sum==a) return
true; return
false;}int
main(){ __int64
p,a; while(scanf("%I64d%I64d",&p,&a)!=EOF) { if(p==a&&p==0) break; if(isprime(p)) printf("no\n"); else if(fun(a,p,p)) printf("yes\n"); else
printf("no\n"); } return
0;} |
原文：http://www.cnblogs.com/zhangdashuai/p/3700908.html