poj_3641_Pseudoprime numbers
2024-09-04 18:22:36
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 2 < p ≤ 1000000000 and 1 < 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
3 2
10 3
341 2
341 3
1105 2
1105 3
0 0
Sample Output
no
no
yes
no
yes
yes 题意:费马定理给出a^p=a mod p(p为素数),一些合数也有类似的状况,判断输入p,a
先判断 p是否为素数,后判断是否满足定理
#include<iostream>
#include<cstdio>
#define LL long long
#define N 100000
using namespace std;
int prime[N];
int pn=0;
bool vis[N];
LL pow(LL a,LL n,LL mod)
{
LL base=a,ret=1;
while(n)
{
if(n&1) ret=(ret*base)%mod;
base=(base*base)%mod;
n>>=1;
}
return ret%mod;
}
bool judge(int n)
{
for(int i=0;prime[i]*prime[i]<=n;i++)
{
if(n%prime[i]==0)
return 1;
}
return 0;
}
int main()
{
for (int i = 2; i < N; i++) {
if (vis[i]) continue;
prime[pn++] = i;
for (int j = i; j < N; j += i)
vis[j] = 1;
}
int a,p;
while(~scanf("%d%d",&p,&a),a&&p)
{
if(!judge(p)){
puts("no");
continue;
}
if(pow(a,p,p)%p==a)
puts("yes");
else
puts("no"); }
}
最新文章
- 给缺少Python项目实战经验的人
- Magento 新增字段的值读写丢失原因
- Java数组课后作业
- springmvc学习笔记---idea创建springmvc项目
- iOS抗锯齿的方式
- bootm命令中地址参数,内核加载地址以及内核入口地址
- hdoj 1406 完数
- IE6、7 a链接内图片加滤镜后导致a标签链接失效问题解决
- cocos2d-x2.2.3和android平台环境的搭建
- Redis源代码分析(二十)--- ae事件驱动
- Hibernate分页查询小结
- 入门vue----(介绍)
- python-三级菜单-67
- HTML5学习路线导航
- hdu 1704 Rank (floyd闭包)
- 话说extern和static
- IAM页面是在统一区分配的还是在混合区分配的?
- MVC摘记
- 【appium】根据class_name定位元素
- <;span>;和<;div>;标签的隐藏和显示切换