POJ 1811 大素数判断
2018-06-17 23:37:53来源:未知 阅读 ()
数据范围很大,用米勒罗宾测试和Pollard_Rho法可以分解大数。
模板在代码中 O.O
#include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> using namespace std; __int64 pri[]= {2,3,5,7,11,13,17,19,23,29,31};//用小素数表做随机种子避免第一类卡米歇尔数的误判 __int64 multi(__int64 a,__int64 b,__int64 n) //乘法快速幂 { __int64 tmp=0; while(b) { if(b&1) { tmp+=a; if(tmp>=n) tmp-=n; } a<<=1; if(a>=n) a-=n; b>>=1; } return tmp; } __int64 multimod(__int64 a,__int64 m,__int64 n) //乘法快速幂 { __int64 tmp=1; a%=n; while(m) { if(m&1) tmp=multi(tmp,a,n); a=multi(a,a,n); m>>=1; } return tmp; } __int64 gcd(__int64 a, __int64 b) //迭代算法 { while(b) { __int64 c=a%b; a=b; b=c; } return a; } bool Miller_Rabin(__int64 n) //大素数判断 { if(n<2) return false; if(n==2) return true; if(!(n&1)) return false; __int64 k=0,j,m,a; m=n-1; while(!(m&1)) { m>>=1; k++; } for(int i=0; i<10; i++) { if(pri[i]>=n) return true; a=multimod(pri[i],m,n); if(a==1) continue; for(j=0; j<k; j++) { if(a==n-1) break; a=multi(a,a,n); } if(j==k) return false; } return true; } __int64 pollard_rho(__int64 c,__int64 n) //查找因数 { __int64 i,x,y,k,d; i=1; x=y=rand()%n; k=2; do { i++; d=gcd(n+y-x,n); if(d>1 && d<n) return d; if(i==k) { y=x; k<<=1; } x=(multi(x,x,n)+n-c)%n; } while(y!=x); return n; } __int64 rho(__int64 n) { if(Miller_Rabin(n)) return n; __int64 t=n; while(t>=n) t=pollard_rho(rand()%(n-1)+1,n); __int64 a=rho(t); __int64 b=rho(n/t); return a<b? a:b; } __int64 ans[10000005],flag; void rhoAll(__int64 n) //计算全部质因子 { if(Miller_Rabin(n)) { ans[flag++]=n; return; } __int64 t=n; while(t>=n) t=pollard_rho(rand()%(n-1)+1,n); rhoAll(t); rhoAll(n/t); return; } int main() { //freopen("in.txt","r",stdin); int t; __int64 n; scanf("%d",&t); while(t--) { flag=0; scanf("%I64d",&n); if(Miller_Rabin(n)) printf("Prime\n"); else { //rhoAll(n); printf("%I64d\n",rho(n)); } /*for(int i=0;i<flag;i++) //输出全部质因子 if(i!=flag-1) printf("%I64d ",ans[i]); else printf("%I64d\n",ans[i]);*/ } return 0; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:A 钟表类
下一篇:[C++]基数排序的实现
- POJ-3278 2020-04-01
- Asteroids!_poj2225 2020-02-09
- poj-1753题题解思路 2020-01-26
- POJ1852 2019-11-11
- POJ2431 优先队列+贪心 - biaobiao88 2019-11-03
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash