Description

Input

第一行：CAS,代表數(shù)據(jù)組數(shù)（不大于350），以下CAS行，每行一個(gè)數(shù)字，保證在64位長(zhǎng)整形范圍內(nèi)，并且沒(méi)有負(fù)數(shù)。你需要對(duì)于每個(gè)數(shù)字：第一，檢驗(yàn)是否是質(zhì)數(shù)，是質(zhì)數(shù)就輸出PRime 第二，如果不是質(zhì)數(shù)，輸出它最大的質(zhì)因子是哪個(gè)。 

Output

第一行CAS(CAS<=350，代表測(cè)試數(shù)據(jù)的組數(shù)) 以下CAS行：每行一個(gè)數(shù)字，保證是在64位長(zhǎng)整形范圍內(nèi)的正數(shù)。 對(duì)于每組測(cè)試數(shù)據(jù)：輸出Prime，代表它是質(zhì)數(shù)，或者輸出它最大的質(zhì)因子，代表它是和數(shù) 

Sample Input

Sample Output

HINT

數(shù)據(jù)范圍： 保證cas<=350，保證所有數(shù)字均在64位長(zhǎng)整形范圍內(nèi)。 

Source

題解：Miller_rabbin+Pollard rho

這道題時(shí)限卡的喪心病狂，不能用快速乘，否則會(huì)TLE

#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#define LL long long using namespace std;LL n,mx;LL mul(LL a,LL b,LL p){    /*LL ans=0; LL base=a%p;    while (b) {        if (b&1) ans=(ans+base)%p;        b>>=1;        base=(base+base)%p;    }    return ans;*/    LL tmp=(a*b-(LL)((long double)a/p*b+1e-8)*p);    return tmp<0?tmp+p:tmp;}LL quickpow(LL num,LL x,LL p){    LL ans=1; LL base=num%p;    while (x) {        if (x&1) ans=mul(ans,base,p);        x>>=1;        base=mul(base,base,p);    }    return ans;}bool miller_rabbin(LL n){    if (n==2) return true;    if (n<=1||!(n&1)) return false;    LL t=0,a,x,y,u=n-1;    while (!(u&1)) t++,u>>=1;    for (int i=0;i<=10;i++) {        a=rand()*rand()%(n-1)+1;        x=quickpow(a,u,n);        for (int j=0;j<t;j++) {            y=mul(x,x,n);            if (y==1&&x!=1&&x!=n-1) return false;            x=y;        }        if (x!=1) return false;    }    return true;}LL gcd(LL x,LL y){    LL r;    while (y) {        r=x%y;        x=y; y=r;    }    return x;}LL pollard_rho(LL n,LL c){    LL k=2;    LL x=rand()%n,y=x,p=1;    for(LL i=1;p==1;i++)    {        x=(mul(x,x,n)+c)%n;        p=y>x?y-x:x-y;        p=gcd(n,p);        if(i==k)y=x,k+=k;    }    return p;}void solve(LL n){    if (n==1) return;    if (miller_rabbin(n)) {        mx=max(mx,n);        return;    }    LL p=n;     while (p==n) p=pollard_rho(p,rand()%(n-1)+1);    solve(p); solve(n/p);}int main(){    srand(2000001001);    int T; scanf("%d",&T);    while (T--) {        scanf("%lld",&n);        //cout<<n<<endl;        mx=0;        solve(n);        if (mx==n) puts("Prime");        else printf("%lld/n",mx);    }}