poj Pseudoprime numbers 3641
2024-10-22 13:33:22
Pseudoprime numbers
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 10903 | Accepted: 4710 |
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 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,使得a^p==a mod(p)的p称为伪质数。
思路:快速幂运算验证即可。
AC代码:
#define _CRT_SECURE_NO_DEPRECATE
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
#include<string>
#include<bitset>
using namespace std;
#define INF 0x3f3f3f3f
#define MOD 1000000000
typedef long long ll;
const int N_MAX = ;
ll p, a;
ll ll_mult(ll a,ll x,ll p) {
ll res = ; bitset<>tmp = static_cast<bitset<>>(x);//前面低位
for (int i = ; i < tmp.size();i++) {
if (tmp[i])res += a*( << i);
res %= p;
} return res;
} ll mod_pow(ll x,ll n,ll p) {
ll res = ;
while (n) {
if (n & )res = ll_mult(res,x,p);
x = ll_mult(x, x,p);
n >>= ;
}
return res;
} bool is_prime(ll n) {
for (int i = ; i*i <= n;i++) {
if (n%i == )return false;
}
return n!=;
} int main() {
while (scanf("%lld%lld",&p,&a)&&(p||a)) {
if (is_prime(p)) { puts("no"); continue; }
if (mod_pow(a, p, p) == a)puts("yes");
else puts("no");
} return ;
}
最新文章
- Notepad++编写Markdown
- MAC PRO 的网关在哪里
- segues的类型
- linux下vim命令详解
- oschina数据库相关
- JavaEE(9) - Session EJB的生命周期、事务及拦截器
- Android ViewDragHelper完全解析 自定义ViewGroup神器
- 基于Spring-WS的Restful API的集成测试
- Python基础_函数2
- Floor报错原理分析
- Map接口----Map中嵌套Map
- docker构建本地仓库后,无法登陆解决办法(CentOS/Ubuntu)
- [jquery]如何实现页面单块DIV区域滚动展示
- 免费SVN、Git项目托管主机推荐
- 11.21 CSS学习-下午
- 12-mapReduce的简介和yarn搭建
- 《TCP/IP具体解释卷2:实现》笔记--接口层
- Expected indentation of 0 spaces but found 2
- 3dContactPointAnnotationTool开发日志(十一)
- 大全Kafka Streams
热门文章
- 自行实现一个简易RPC框架
- ssh整合思想 Spring与Hibernate的整合ssh整合相关JAR包下载 .MySQLDialect方言解决无法服务器启动自动update创建表问题
- cppoop作业:Inheritance+Composition 關係下的構造和析構
- B1002 写出这个数
- python数据类型之字符串(str)和其常用方法
- POJ:3020-Antenna Placement(二分图的最小路径覆盖)
- The 2018 ACM-ICPC Chinese Collegiate Programming Contest Fight Against Monsters
- MIP启发式算法:local branching
- SpringMVC之Controller简单使用
- WPF触控程序开发(三)——类似IPhone相册的反弹效果