本文主要是介绍pollard rho，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
http://wenku.baidu.com/link?url=O5zUelUS26sjkR6Uu9Ty3-91tXYH7HEuS2fepWq7PMuH9jjrXa_NLEMNvopHgPdB9uDptolWDlJzpSuwUsDV6pKeJUYEzARbI8Qu4xPdXfK
好文章
poj2429,快速乘，不用TL。。。
#include<iostream>
#include<ctime>
#include<algorithm>
#include<cmath>
#include<cstdio>
using namespace std;
long long p,f[1000],ans;
long long f2[1000],q;
long long mod2(long long a,long long b,long long n)
{long long exp = a%n, res = 0;while(b){if(b&1){res += exp;if(res>n) res -= n;}exp <<= 1;if(exp>n) exp -= n;b>>=1;}return res;
}long long pow_mod(long long a,long long b,long long m)
{long long exp=a%m, res=1;while(b>=1){if(b&1)res=mod2(res,exp,m);exp = mod2(exp,exp,m);b>>=1;}return res;
}
bool miller(long long k,long long d,long long n,long long a)
{if(n==2||n==a) return true;if(!(n&1)) return false;long long i,t=pow_mod(a,d,n);if(t==1) return true;for(i=0;i<k;i++){if(t==n-1) return true;t=(t*t)%n;}return false;
}
bool judge(long long n)
{if(n<2) return false;long long k=0,d=n-1;while(!(d&1)){k++;d>>=1;}if(n<1373653){if(miller(k,d,n,2)&&miller(k,d,n,3)) return true;return false;}if(n<9080191){if(miller(k,d,n,31)&&miller(k,d,n,73)) return true;return false;}if(n<4759123141){if(miller(k,d,n,2)&&miller(k,d,n,3)&&miller(k,d,n,5)&&miller(k,d,n,11)) return true;return false;}if(n<2152302898747){if(miller(k,d,n,2)&&miller(k,d,n,3)&&miller(k,d,n,5)&&miller(k,d,n,7)&&miller(k,d,n,11)) return true;return false;}else{if(miller(k,d,n,2)&&miller(k,d,n,3)&&miller(k,d,n,5)&&miller(k,d,n,7)&&miller(k,d,n,11)&&miller(k,d,n,31)&&miller(k,d,n,61)&&miller(k,d,n,73)) return true;return false;}
}
long long gcd(long long a,long long b){long long c;while(b){c=b; b=a%b; a=c;}return a;
}
long long pollard_rho(long long n,long long k){srand(time(0));long long x=rand()%(n-1)+1;long long i=1,t=2,y=x,d;while(1){i++;x=(mod2(x,x,n)+k)%n;d=gcd(y-x,n);if(d>1 && d<n) return d;if(x==y) return n;if(t==i) y=x,t<<=1;}
}
void get_factor(long long n,long long k){if(judge(n)){f[p++]=n;return ;}long long h=n;while(h>=n)h=pollard_rho(h,k--);get_factor(h,k);get_factor(n/h,k);
}
void dfs(long long i,long long x,long long k){if(i>q) return ;if(x>ans && x<=k) ans=x;dfs(i+1,x,k);x*=f2[i];if(x>ans && x<=k) ans=x;dfs(i+1,x,k);
}
int main(int argc, char** argv) {long long m,n,k;while(scanf("%lld%lld",&m,&n)!=-1){if(m==n){printf("%lld %lld\n",m,n); continue;}k=n/m; p=0; q=0; ans=1;get_factor(k,180);sort(f,f+p);f2[0]=f[0];for(int i=0;i<p-1;i++)if(f[i]==f[i+1]) f2[q]*=f[i+1];else{q++; f2[q]=f[i+1];}long long tmp=(long long)sqrt(k*1.0);dfs(0,1,tmp);printf("%lld %lld\n",m*ans,k/ans*m);}return 0;
}
这篇关于pollard rho的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
