nefu120梅森素数
2021/7/30 23:37:36
本文主要是介绍nefu120梅森素数,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
#include<iostream> #include<cstdio> using namespace std; typedef long long ll; const int maxn = 63; ll multi(ll a,ll b,ll mod_val)//实现a * b % mod_val的操作(大数乘法换成加法,否则直接乘会爆) { a = a % mod_val; b = b % mod_val; ll ans = 0; while(b) { if(b & 1) { ans = (ans + a) % mod_val; } b >>= 1; a = (a <<= 1) % mod_val; } return ans; } bool is_meiprime(ll n,int p) { ll t = 4; for(int i = 2; i <= p - 1; i ++)//求出R[p - 1] { t = (multi(t,t,n) - 2 ) % n ; } t %= n; if(t == 0)//素数:r_{p-1}\equiv 0(mod M_p) return true; return false; } int main() { int Tcase; scanf("%d",&Tcase); for(int ii = 1; ii <= Tcase; ii ++) { int p; scanf("%d",&p); if(p == 2)//当为2的时候需要特判 { cout << "yes" << endl; continue; } ll sum = 1; sum <<= p; sum --;//sum 为求出的梅森数 if(is_meiprime(sum,p)) cout << "yes" << endl; else cout << "no" << endl; } return 0; }
这篇关于nefu120梅森素数的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-28微服务架构中API版本控制的实践
- 2024-09-28AI给的和自己写的Python代码,都无法改变输入框的内容,替换也不行
- 2024-09-27Sentinel配置限流资料:新手入门教程
- 2024-09-27Sentinel配置限流资料详解
- 2024-09-27Sentinel限流资料:新手入门教程
- 2024-09-26Sentinel限流资料入门详解
- 2024-09-26Springboot框架资料:初学者入门教程
- 2024-09-26Springboot框架资料详解:新手入门教程
- 2024-09-26Springboot企业级开发资料:新手入门指南
- 2024-09-26SpringBoot企业级开发资料新手指南