[POJ1811]Prime Test
发布时间:2020-12-14 04:24:57 所属栏目:大数据 来源:网络整理
导读:题目:Prime Test 传送门:http://poj.org/problem?id=1811 分析: miller-Rabin测试和Pollard-rho算法? 的裸题啦 abs关于longlong 自动进行了类型强制转换,Wa了一万发。 #include ctime #include cstdio #include cstdlib #include algorithm #include ios
题目:Prime Test 传送门:http://poj.org/problem?id=1811 分析: miller-Rabin测试和Pollard-rho算法? 的裸题啦 abs关于longlong 自动进行了类型强制转换,Wa了一万发。 #include <ctime> #include <cstdio> #include <cstdlib> #include <algorithm> #include <iostream> using namespace std; typedef long long LL; LL ksc(LL a,LL n,LL mod){ LL ret=0; for(;n;n>>=1){ if(n&1){ret+=a;if(ret>=mod)ret-=mod;} a<<=1;if(a>=mod)a-=mod; } return ret; } LL ksm(LL a,LL mod){ LL ret = 1; for(;n;n>>=1){ if(n&1)ret=ksc(ret,a,mod); a=ksc(a,mod); } return ret; } int millerRabin(LL n){ if(n<2 || (n!=2 && !(n&1)))return 0; LL d=n-1;for(;!(d&1);d>>=1); for(int i=0;i<20;++i){ LL a=rand()%(n-1)+1; LL t=d,m=ksm(a,d,n); for(;t!=n-1 && m!=1 && m!=n-1;m=ksc(m,m,n),t<<=1); if(m!=n-1 && !(t&1)) return 0; } return 1; } LL cnt,fact[100]; LL gcd(LL a,LL b){return !b?a:gcd(b,a%b);} LL pollardRho(LL n,int a){ LL x=rand()%n,y=x,d=1,k=0,i=1; while(d==1){ ++k; x=ksc(x,x,n)+a;if(x>=n)x-=n; d=gcd(x>y?x-y:y-x,n); if(k==i){y=x;i<<=1;} } if(d==n)return pollardRho(n,a+1); return d; } void findfac(LL n){ if(millerRabin(n)){fact[++cnt]=n;return;} LL p=pollardRho(n,rand()%(n-1)+1); findfac(p); findfac(n/p); } int main(){ srand(time(0)); int T;scanf("%d",&T); for(LL n;T--;){ scanf("%lld",&n); if(millerRabin(n))puts("Prime"); else{ cnt=-1; findfac(n); LL ans=fact[0]; for(int i=1;i<=cnt;++i)ans=std::min(fact[i],ans); printf("%lldn",ans); } } return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |