Description
Fermat's theorem states that for any prime number p and for any integer a > 1, ap = a (mod p). That is, if we raise a to the pth power and divide by p, the remainder is a. Some (but not very many) non-prime values of p, known as base-a pseudoprimes, have this property for some a. (And some, known as Carmichael Numbers, are base-a pseudoprimes for all a.) Given < p ≤ and < a < p, determine whether or not p is a base-a pseudoprime.
Input
Input contains several test cases followed by a line containing "0 0". Each test case consists of a line containing p and a.
Output
For each test case, output "yes" if p is a base-a pseudoprime; otherwise output "no".
Sample Input
Sample Output
no
no
yes
no
yes
yes
Source
Waterloo Local Contest, 2007.9.23
感觉好久没A题了，脑子都快生锈了，所有赶紧做做题。
求(a^p)%p==a,数据大所有用long long
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<math.h>
#include<algorithm>
#include<queue>
#include<set>
#include<bitset>
#include<map>
#include<vector>
#include<stdlib.h>
#include <stack>
using namespace std;
#define PI acos(-1.0)
#define max(a,b) (a) > (b) ? (a) : (b)
#define min(a,b) (a) < (b) ? (a) : (b)
#define ll long long
#define eps 1e-10
#define N 1000000
#define inf 1e12
ll pow_mod(ll a,ll n,ll MOD)
{
if(n==)
return %MOD;
ll tt=pow_mod(a,n>>,MOD);
ll ans=tt*tt%MOD;
if(n&)
ans=ans*a%MOD;
return ans;
}
int main()
{
ll p,a;
while(scanf("%I64d%I64d",&p,&a)==){
if(p== && a==){
break;
}
int flag=;
for(int i=;i<(int)sqrt(p+0.5);i++){
if(p%i==){
flag=;
break;
}
}
if(flag==){
printf("no\n");
continue;
}
ll ans=pow_mod(a,p,p); //printf("%I64d\n",ans);
if(ans==a){
printf("yes\n");
}else{
printf("no\n");
}
}
return ;
}