Hdu 4344 Mark the Rope —— 大数分解，Pollard-Rho模板

本文主要是介绍Hdu 4344 Mark the Rope —— 大数分解，Pollard-Rho模板，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

This way

题意：

问你一个大数有多少个质因子，并且求唯一分解之后每个质因子的最高次的和

题解：

Pollard-Rho模板，用到了Miller_Rabin判素数。

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
ll add(ll a,ll b,ll mod){if(a+b>=mod)return a+b-mod;return a+b;
}
ll qmul(ll a,ll b,ll mod){ll ans=0;for(;b;b>>=1,a=add(a,a,mod))if(b&1)ans=add(ans,a,mod);return ans;}
ll qpow(ll a,ll b,ll mod){ll ans=1;for(;b;b>>=1,a=qmul(a,a,mod))if(b&1)ans=qmul(ans,a,mod);return ans;}
bool Miller_Rabin(ll n)//Miller-Rabin素数检测算法
{ll i,j,a,x,y,t,u,s=10;if(n==2)return true;if(n<2||!(n&1))return false;for(t=0,u=n-1;!(u&1);t++,u>>=1);//n-1=u*2^tfor(i=0;i<s;i++){a=rand()%(n-1)+1;x=qpow(a,u,n);for(j=0;j<t;j++){y=qmul(x,x,n);if(y==1&&x!=1&&x!=n-1)return false;x=y;}if(x!=1)return false;}return true;
}ll Pollard_Rho(ll n,ll c)
{ll i=1,j=2,x=rand()%(n-1)+1,y=x;//随机初始化一个基数（p1）while(1){i++;x=(qmul(x,x,n)+c)%n;//玄学递推ll p=__gcd((y-x+n)%n,n);if(p!=1&&p!=n)return p;//判断if(y==x)return n;//y为x的备份，相等则说明遇到圈，退出if(i==j){y=x;j<<=1;}//更新y，判圈算法应用}
}
vector<ll>vec;
ll num,ans;
void find(ll n,ll c)//同上，n为待分解数，c为随机常数
{if(n==1)return;if(Miller_Rabin(n))//n为质数{vec.push_back(n);//printf("%lld\n",n);return;}ll x=n,k=c;while(x==n)x=Pollard_Rho(x,c++);//当未分解成功时，换个c带入算法find(n/x,k);find(x,k);//递归操作
}int main(){int t;scanf("%d",&t);while(t--){num=ans=0;vec.clear();ll n;scanf("%lld",&n);find(n,rand());sort(vec.begin(),vec.end());int j=0;for(int i=0;i<vec.size();i=j){ll ret=1;num++;while(j<vec.size()&&vec[i]==vec[j])ret*=vec[j++];ans+=ret;}if(num==1)ans=ans/vec[0];printf("%lld %lld\n",num,ans);}return 0;
}