问题描述：素性测试兼质因子分解
解题关键：pollard-rho质因数分解，在RSA的破译中也起到了很大的作用
期望复杂度：$O({n^{frac{1}{4}}})$
#include<cstdio> #include<cstring> #include<algorithm> #include<cstdlib> #include<iostream> #include<cmath> #include<vector> #define inf 1ll<<61 typedef long long ll; using namespace std; const int S=20; ll fac[100000],tol,mi; ll mod_mul(ll a,ll b,ll p){ ll res=0; a%=p,b%=p; while(b){ if(b&1)res=(res+a)%p; a=(a<<1)%p; b>>=1; } return res; } ll mod_pow(ll x,ll n,ll p){ ll res=1; while(n){ if(n&1)res=mod_mul(res,x,p); x=mod_mul(x,x,p); n>>=1; } return res; } bool check(ll a,ll n,ll x,ll t){//判断是否为合数 ll ret=mod_pow(a,x,n); ll last=ret; for(int i=1;i<=t;i++){ ret=mod_mul(ret,ret,n); if(ret==1&&last!=1&&last!=n-1)return 1; last=ret; } if(ret!=1)return 1;//fermat测试 return 0; } bool Miller_Rabin(ll n){ if(n<2)return 0; if(n==2)return 1; if((n&1)==0)return 0; ll x=n-1,t=0; while((x&1)==0)x>>=1,t++; for(int i=0;i<S;i++){ ll a=rand()%(n-1)+1; if(check(a,n,x,t))return 0;//合数 } return 1; } ll Pollard_Rho(ll n,ll c){//返回值n的因子 ll i=1,j=2,x=rand()%(n-1)+1,y=x; while(1){ i++,x=(mod_mul(x,x,n)+c)%n; ll p=__gcd((y-x+n)%n,n); if(p!=1&&p!=n)return p;//p本身是合数,分解为本身就无意义了 if(y==x)return n;//循环节只有1,不符合条件,同时也判圈了 if(i==j)y=x,j<<=1;//这里控制1步和2步 } } void find1(ll n,ll c){//找因子主体 if(n==1) return; if(Miller_Rabin(n)){ fac[tol++]=n; mi=min(mi,n); return; } ll p=n,k=c; while(p>=n)p=Pollard_Rho(p,c--);//返回的是小于n但不一定为素数的因子 find1(p,k); find1(n/p,k); } 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{ find1(n,12312); cout<<mi<<endl; } } return 0; }