模板题
注意Pollard_Rho()的写法
第一次比较应该是 a-0步,b-1步
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using std::max;
typedef long long ll;
int T;
ll N;
ll Pri[10]={2LL, 3LL, 5LL, 7LL, 11LL, 13LL, 17LL, 19LL, 23LL, 29LL};
ll Rand(){
return rand()*1034567890LL+(ll)(rand());
}
ll Rand(ll l, ll r){
return Rand()%(r-l+1LL)+l;
}
ll abs(ll a){
return (a>0LL)?a:(-a);
}
ll gcd(ll a, ll b){
return (b==0LL)?a:gcd(b, a%b);
}
ll MOD;
ll sr;
ll sum(ll a, ll b){
sr=a+b;
if(sr>=MOD) sr-=MOD;
return sr;
}
ll mul(ll a, ll b){
ll k=(ll)((1.0L*a*b)/(1.0L*MOD));
ll r=a*b-k*MOD;
if(r<0) r+=MOD;
return r;
}
ll pow(ll a, ll k){
ll ret=1LL, t=a;
while(k>0LL){
if(k&1LL) ret=mul(ret, t);
t=mul(t, t);
k>>=1;
}
return ret;
}
bool Miller_Rabin(ll n){
if(n<2LL) return false;
if(n==2LL) return true;
if((n&1LL)==0LL) return false;
MOD=n;
int k=0;
ll m=n-1, a;
while((m&1LL)==0LL) {++k;m>>=1;}
bool ret=true;
for(int i=0, j;i<10 && ret;++i){
if(Pri[i]>=n) break;
a=pow(Pri[i], m);
if(a==1LL) continue;
for(j=0;j<k;++j){
if(a==n-1LL) break;
a=mul(a, a);
}
if(j==k) ret=false;
}
return ret;
}
ll Pollard_Rho(ll c, ll n){
MOD=n;
ll a=Rand(1LL, n-1LL), b=sum(mul(a, a), c), d;
while(a!=b){
d=gcd(abs(a-b), n);
if(d>1LL) return d;
a=sum(mul(a, a), c);
b=sum(mul(b, b), c);b=sum(mul(b, b), c);
}
return n;
}
ll Rho(ll n){
if(Miller_Rabin(n)) return n;
ll t=n;
while(t==n) t=Pollard_Rho(Rand(1LL, n-1LL), n);
return max(Rho(t), Rho(n/t));
}
int main(){
srand(1075757);
scanf("%d", &T);
while(T--){
scanf("%lld", &N);
if(Miller_Rabin(N)) puts("Prime");
else printf("%lld\n", Rho(N));
}
return 0;
}