【POJ - 3641】Pseudoprime numbers (快速幂)

时间:2022-08-07 12:35:54

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 ;
}