poj1811 + hdu4344 (素数测试及大数分解)
发布时间:2020-12-14 04:04:42 所属栏目:大数据 来源:网络整理
导读:就是大素数判断和大数分解问题,具体思路详询算法导论和Matrix67的博客 素数与素性测试 ? 题目:poj 1811 prime test? 思路:根据pollard rho启发式算法求出某一个非平凡因子。 #include cstdio#include iostream#include cstring#include algorithm#include
就是大素数判断和大数分解问题,具体思路详询算法导论和Matrix67的博客素数与素性测试? 题目:poj 1811 prime test? 思路:根据pollard rho启发式算法求出某一个非平凡因子。 #include <cstdio> #include <iostream> #include <cstring> #include <algorithm> #include <cmath> #include <map> #include <cstdlib> using namespace std; #define Times 10 map<long long,int>m; long long mi; long long random(long long n) { return ((double)rand()/RAND_MAX*n+0.5); } long long multi(long long a,long long b,long long mod) { long long ans=0; while(b) { if(b&1) { b--; ans=(ans+a)%mod; } else { b/=2; a=(2*a)%mod; } } return ans; } long long Pow(long long a,long long mod) { long long ans=1; while(b) { if(b&1) { b--; ans=multi(ans,a,mod); } else { b/=2; a=multi(a,mod); } } return ans; } bool witness(long long a,long long n) { long long d=n-1; while(!(d&1)) d>>=1; long long t=Pow(a,d,n); while(d!=n-1 && t!=1 && t!=n-1) { t=multi(t,t,n); d<<=1; } return t==n-1 || d&1; } bool miller_rabin(long long n) { if(n==2) return true; if(n<2||!(n&1)) return false; for(int i=1;i<=Times;i++) { long long a=random(n-2)+1; if(!witness(a,n)) return false; } return true; } long long gcd(long long a,long long b) { if(b==0) return a; return gcd(b,a%b); } long long pollard_rho(long long n,int c) { long long x,y,i=1,k=2; x=random(n-2)+1; y=x; while(1) { i++; x=(multi(x,x,n)+c)%n; d=gcd(y-x,n); if(1<d&&d<n) return d; if(y==x) return n; if(i==k) { y=x; k<<=1; } } } void find(long long n,int c) { if(n==1) return ; if(miller_rabin(n)) { //m[n]++; mi=min(mi,n); return ; } long long p=n; while(p>=n) p=pollard_rho(p,c--); find(p,c); find(n/p,c); } int main() { int t; scanf("%d",&t); while(t--) { long long n; scanf("%lld",&n); mi=n; if(miller_rabin(n)) cout<<"Prime"<<endl; else { find(n,12312); cout<<mi<<endl; } } return 0; } 题目:hdu 4344 Mark the rope 思路:用递归通过pollard rho进行质因式分解,然后用map存起来(用map的话时间可能会多点,G++可以过,C++会超时) #include <cstdio> #include <iostream> #include <algorithm> #include <cmath> #include <cstring> #include <map> using namespace std; #define Times 10 typedef __int64 LL; map<LL,int>m; LL Random(LL n) { return ((double)rand()/RAND_MAX*n+0.5); } LL multi(LL a,LL b,LL mod) { LL ans=0; while(b) { if(b&1) { b--; ans=(ans+a)%mod; } else { b/=2; a=(a+a)%mod; } } return ans; } LL Pow(LL a,LL mod) { LL ans=1; while(b) { if(b&1) { b--; ans=multi(ans,mod); } } return ans; } bool witness(LL a,LL n) { LL d=n-1; while(!(d&1)) d>>=1; LL t=Pow(a,n); d<<=1; } return t==n-1 || d&1; } bool miller_rabin(LL n) { if(n==2) return true; if(n<2||!(n&1)) return false; for(int i=1;i<=Times;i++) { LL a=Random(n-2)+1; if(!witness(a,n)) return false; } return true; } LL gcd(LL a,LL b) { if(b==0) return a; return gcd(b,a%b); } LL pollard_rho(LL n,LL c) { LL x,k=2; x=Random(n-1)+1; y=x; while(1) { i++; x=(multi(x,n); if(1<d&&d<n) return d; if(y==x) return n; if(i==k) { y=x; k<<=1; } } } void find(LL n,LL c) { if(n==1) return ; if(miller_rabin(n)) { m[n]++; return ; } LL p=n; while(p>=n) p=pollard_rho(p,c); } int main() { int t; cin>>t; while(t--) { LL n; cin>>n; m.clear(); find(n,2013724); if(m.size()==1) cout<<1<<" "<<n/m.begin()->first<<endl; else { LL ans=0; map<LL,int>::iterator it=m.begin(); for(;it!=m.end();it++) ans+=Pow(it->first,it->second,n); cout<<m.size()<<" "<<ans<<endl; } } return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |