Pseudoprime numbers
Descriptions
费马定理指出，对于任意的素数 p 和任意的整数 a > 1，满足 ap = a (mod p) 。也就是说，a的 p 次幂除以 p 的余数等于 a 。p 的某些 (但不是很多) 非素数的值，被称之为以 a 为底的伪素数，对于某个 a 具有该特性。并且，某些 Carmichael 数，对于全部的 a 来说，是以 a为底的伪素数。
给定 2 < p ≤ 1000000000 且 1 < a < p ，判断 p 是否为以 a 为底的伪素数。
输入
输入包含多个测试用例，以 "0 0" 表示输入结束。每个测试用例，由包含 p 和 a 的一行组成。
输出
对于每个测试用例，如果 p 是以 a 为底的伪素数，则输出 "yes"，否则输出 "no" 。
示例输入
3 2
10 3
341 2
341 3
1105 2
1105 3
0 0
示例输出
no
no
yes
no
yes
yes
题目链接
https://vjudge.net/problem/POJ-3641
简单的说满足两个条件
1、p不是素数
2、a的p次幂除以p的余数等于a
就输出yes
否则输出no
AC代码
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#include <sstream>
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define Mod 1000000007
#define eps 1e-6
#define ll long long
#define INF 0x3f3f3f3f
#define MEM(x,y) memset(x,y,sizeof(x))
#define Maxn 100000+100
using namespace std;
ll a,p;
ll mod;
ll qpow(ll a, ll n)//计算a^n % mod
{
ll re = ;
while(n)
{
if(n & )//判断n的最后一位是否为1
re = (re * a) % mod;
n >>= ;//舍去n的最后一位
a = (a * a) % mod;//将a平方
}
return re % mod;
}
int main()
{
while(cin>>p>>a,a+p)
{
ll sum=;
for(ll i=; i*i<p; i++)//判断是否是素数
{
if(p%i==)
sum++;
}
if(sum==)//p是素数
cout<<"no"<<endl;
else//p不是素数
{
mod=p;
if(qpow(a,p)==a)//a的p次幂除以p的余数是否等于a
cout<<"yes"<<endl;
else
cout<<"no"<<endl;
}
}
return ;
}