首页 > 代码库 > hihocoder 1287 : 数论一·Miller-Rabin质数测试 大质数判定
hihocoder 1287 : 数论一·Miller-Rabin质数测试 大质数判定
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
小Hi和小Ho最近突然对密码学产生了兴趣，其中有个叫RSA的公钥密码算法。RSA算法的计算过程中，需要找一些很大的质数。
小Ho：要如何来找出足够大的质数呢？
小Hi：我倒是有一个想法，我们可以先随机一个特别大的初始奇数，然后检查它是不是质数，如果不是就找比它大2的数，一直重复，直到找到一个质数为止。
小Ho：这样好像可行，那我就这么办吧。
过了一会儿，小Ho拿来了一张写满数字的纸条。
小Ho：我用程序随机生成了一些初始数字，但是要求解它们是不是质数太花时间了。
小Hi：你是怎么做的啊？
说着小Hi接过了小Ho的纸条。
小Ho：比如说我要检测数字n是不是质数吧，我就从2开始枚举，一直到sqrt(n)，看能否被n整除。
小Hi：那就对了。你看纸条上很多数字都是在15、16位左右，就算开方之后，也有7、8位的数字。对于这样大一个数字的循环，显然会很花费时间。
小Ho：那有什么更快速的方法么？
小Hi：当然有了，有一种叫做Miller-Rabin质数测试的算法，可以很快的判定一个大数是否是质数。
提示：Miller-Rabin质数测试
输入
第1行：1个正整数t，表示数字的个数，10≤t≤50
第2..t+1行：每行1个正整数，第i+1行表示正整数a[i]，2≤a[i]≤10^18
输出
第1..t行：每行1个字符串，若a[i]为质数，第i行输出"Yes"，否则输出"No"
- 样例输入
- 3
- 3
- 7
- 9
- 样例输出
- Yes
- Yes
- No
- 裸模板题直接套模板
#include <iostream>#include <cstring>#include <cstdio>#include <algorithm>#include <queue>#include <vector>#include <iomanip>#include <math.h>#include <map>using namespace std;#define FIN freopen("input.txt","r",stdin);#define FOUT freopen("output.txt","w",stdout);#define INFLL 0x3f3f3f3f3f3f3f#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1typedef long long LL;typedef pair<int, int> PII;LL multi(LL a, LL b, LL mod) { LL ret = 0; while(b) { if(b & 1) ret = ret + a; if(ret >= mod) ret -= mod; a = a + a; if(a >= mod) a -= mod; b >>= 1; } return ret;}LL power(LL a, LL b, LL mod) { LL ret = 1; while(b) { if(b & 1) ret = multi(ret, a, mod); a = multi(a, a, mod); b >>= 1; } return ret;}bool Miller_Rabin(LL n) { LL u = n - 1, pre, x; int i, j, k = 0; if(n == 2 || n == 3 || n == 5 || n == 7 || n == 11) return true; if(n == 1 || (!(n % 2)) || (!(n % 3)) || (!(n % 5)) || (!(n % 7)) || (!(n % 11))) return false; for(; !(u & 1); k++, u >>= 1); for(i = 0; i < 5; i++) { x = rand() % (n - 2) + 2; x = power(x, u, n); pre = x; for(j = 0; j < k; j++) { x = multi(x, x, n); if(x == 1 && pre != 1 && pre != (n - 1)) return false; pre = x; } if(x != 1) return false; } return true;}int main() { LL a; int T; scanf("%d", &T); while(T--) { scanf("%lld", &a); if(Miller_Rabin(a)) puts("Yes"); else puts("No"); } return 0;}
hihocoder 1287 : 数论一·Miller-Rabin质数测试 大质数判定
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。