原本是想把這個(gè)算法搞懂的，然后在網(wǎng)上看了又看，覺(jué)得，還是有時(shí)間再來(lái)看吧，我錯(cuò)了。

看到了一個(gè)大佬的博客，順帶收集一下板子

這個(gè)板子可以求大數(shù)的最大的因子。

#define LL long long bool IsPrime(LL);//返回素性測(cè)試結(jié)果 LL GCD(LL,LL);//返回兩個(gè)數(shù)的GCD LL Mix(LL,LL,LL);//返回兩個(gè)數(shù)在模運(yùn)算下的乘積void MaxFactor(LL n,LL &ans) {if(n==1||n<=ans||IsPrime(n)){return;//判斷特殊情況：n為1或素?cái)?shù)}for(LL c=rand()%(n-1)+1;;c++){//為防止隨機(jī)數(shù)無(wú)效化，使用死循環(huán)LL t1=rand()%(n-1)+1,t2=(Mix(t1,t1,n)+c)%n;LL p=1,i=0,g=0;while(t1!=t2){p=Mix(p,abs(t1-t2),n);if(!p){//乘積為0時(shí)說(shuō)明找到了一個(gè)因子g=GCD(n,abs(t1-t2));if(g>1&&g<n){MaxFactor(g,ans);MaxFactor(n/g,ans);}return;}++i;if(i==127){//當(dāng)有127個(gè)數(shù)時(shí)強(qiáng)制測(cè)試g=GCD(n,p);if(g>1&&g<n){MaxFactor(g,ans);MaxFactor(n/g,ans);return;}p=1,i=0;}t1=(Mix(t1,t1,n)+c)%n;t2=(Mix(t2,t2,n)+c)%n;t2=(Mix(t2,t2,n)+c)%n;}g=GCD(n,p);if(g>1&&g<n){//循環(huán)退出后收尾MaxFactor(g,ans);MaxFactor(n/g,ans);return;}} }

又找了一個(gè)板子，這個(gè)好像可以求出所有的因子（保存在數(shù)組factor中）

#include<iostream> #include<cmath> #include<cstring> #include<algorithm> #include<cstdio> #include<stdlib.h> #include<time.h> #define times 20 using namespace std; #define ll long long ll total; ll factor[110]; ll qmul(ll a,ll b,ll M){a%=M;b%=M;ll ans=0;while (b){if (b&1){ans=(ans+a)%M;}a=(a<<=1)%M;b>>=1;}return ans%M; }///快乘，因?yàn)閮蓚€(gè)longlong的數(shù)相乘可能會(huì)溢出，所以這里轉(zhuǎn)乘法為加法，思想和快速冪相似 ll qpow(ll a,ll b,ll int M){ll ans=1;ll k=a;while(b){if(b&1)ans=qmul(ans,k,M)%M;k=qmul(k,k,M)%M;b>>=1;}return ans%M; } bool witness(ll a,ll n,ll x,ll sum){ll judge=qpow(a,x,n);if (judge==n-1||judge==1)return 1;while (sum--){judge=qmul(judge,judge,n);if (judge==n-1)return 1;}return 0; } bool miller(ll n){ ///判斷素?cái)?shù)if (n<2)return 0;if (n==2)return 1;if ((n&1)==0)return 0;ll x=n-1;ll sum=0;while (x%2==0){x>>=1;sum++;}for (ll i=1;i<=times;i++){ll a=rand()%(n-1)+1;if (!witness(a,n,x,sum))return 0; ///費(fèi)馬小定理的隨機(jī)數(shù)檢驗(yàn)}return 1; } ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b); } ll pollard(ll n,ll c){ll x,y,d,i=1,k=2;x=rand()%n;y=x;while (1){i++;x=(qmul(x,x,n)+c)%n; ///不斷調(diào)整xd=gcd(y-x,n);if (d<0)d=-d;if (d>1&&d<n)return d; ///找到因子if (y==x)return n; ///找到循環(huán)，返回n，重新來(lái)if (i==k){ ///一個(gè)優(yōu)化y=x;k<<=1;}} } void find(ll n){///尋找這個(gè)數(shù)的素因子，并存起來(lái)if (miller(n)){factor[++total]=n;return ;}ll p=n;while (p>=n) p=pollard(p,rand()%(n-1)+1); ///不斷找因子，知道找到為止，返回n說(shuō)明沒(méi)找到find(n/p);find(p); } int main(){ll n,m,i,t;scanf("%lld",&t);while (t--){scanf("%lld",&n);if (miller(n)) printf("Prime\n");else {memset(factor,0,sizeof(factor));total=0;find(n);sort(factor+1,factor+total+1);printf("%lld\n",factor[1]);}} }

總結(jié)

以上是生活随笔為你收集整理的Pollar Rho算法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。