传送门
Pollard−rhoPollard-rhoPollard−rho板题。
题意简述:给出几个数,让你判断是不是质数,如果不是质数就求出其最大质因子,数的大小为1e181e181e18以内。
先用miller−rabinmiller-rabinmiller−rabin判断是不是素数,然后上Pollard−rhoPollard-rhoPollard−rho质因数分解即可。
代码:
#include<bits/stdc++.h>
#define ri register int
using namespace std;
typedef long long ll;
typedef unsigned int uint;
ll ans;
int pri[10]={2,3,5,7,11,13,17,19,23,29};
inline ll ksc(ll a,ll b,ll mod){return (a*b-(ll)((long double)a/mod*b)*mod+mod)%mod;}
inline ll ksm(ll a,ll p,ll mod){ll ret=1;if(a>=mod)a%=mod;for(;p;p>>=1,a=ksc(a,a,mod))if(p&1)ret=ksc(ret,a,mod);return ret;}
inline bool check(ll x,ll a,ll s,ll t){
a=ksm(a,t,x);
ll p=a;
if(a==1||a==x-1)return 1;
while(s--){
a=ksc(p,p,x);
if(a==1&&(p!=x-1&&p!=1))return 0;
p=a;
}
return p==1;
}
inline bool MRT(ll x){
if(x==2||x==3)return ans=max(ans,x),1;
if(!(x&1))return 0;
if(x%6!=1&&x%6!=5)return 0;
ll s=0,t=x-1;
while(!(t&1))t>>=1,++s;
for(ri i=0;i<10;++i){
if(x==pri[i])return ans=max(ans,x),1;
if(x==x/pri[i]*pri[i])return 0;
if(!check(x,pri[i],s,t))return 0;
}
return ans=max(ans,x),1;
}
inline ll F(ll x,ll c,ll mod){return (ksc(x,x,mod)+c)%mod;}
inline ll gcd(ll a,ll b){while(b){ll t=a;a=b,b=t%a;}return a;}
inline ll rho(ll n,ll c){
ll x=rand()%n+1,y=x,p=1;
for(ri i=1,k=2;p==1;++i){
x=F(x,c,n),p=gcd(y>x?y-x:x-y,n);
if(k==i)y=x,k<<=1;
}
return p;
}
inline void solve(ll n){
if(MRT(n)||n==1)return ;
ll d=rho(n,rand()%n);
while(d==n)d=rho(n,rand()%n);
solve(d),solve(n/d);
}
int main(){
ll n;
int tt;
scanf("%d",&tt);
while(tt--){
ans=0,scanf("%lld",&n);
if(!MRT(n))solve(n),cout<<ans<<'\n';
else puts("Prime");
}
return 0;
}