【BZOJ3667】Rabin-Miller算法（Pollard_pho算法）

Input

第一行：CAS,代表資料組數（不大于350），以下CAS行，每行一個數字，保證在64位長整形範圍内，并且沒有負數。你需要對于每個數字：第一，檢驗是否是質數，是質數就輸出Prime

第二，如果不是質數，輸出它最大的質因子是哪個。

Output

第一行CAS(CAS<=350，代表測試資料的組數)

以下CAS行：每行一個數字，保證是在64位長整形範圍内的正數。

對于每組測試資料：輸出Prime，代表它是質數，或者輸出它最大的質因子，代表它是和數

Sample Input

6

2

13

134

8897

1234567654321

1000000000000

Sample Output

Prime

Prime

67

41

4649

5

HINT

資料範圍：

保證cas<=350，保證所有數字均在64位長整形範圍内。

題解：

模闆題。這是一個比較冷門的但還比較有用的數論知識，不會的可以看：

Miller-Rabin算法&Pollard_pho算法

是裸的模闆，但是出題人硬要卡常非常有趣，但是要優化常數，乘法要自己用long double轉一下，不然會TLE。

模闆：（BZOJ3667）

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<math.h>
#define ll long long
#define inf 0x7f7f7f7f
#define il inline 
using namespace std;
const ll a[]={,,,,,,,,,};
il ll read()
{
    ll x=,f=;
    char c=getchar();
    while(c<'0' || c>'9') {if(c=='-') f=-;c=getchar();}
    while(c<='9' && c>='0') {x=x*+c-'0';c=getchar();}
    return x*f;
}
int n;
ll mx,x; 
ll gcd(ll a,ll b)
{
    if(!b) return a;
    return gcd(b,a%b);
}
il ll mul(ll a,ll b,ll p)
{
    ll tmp=(a*b-(ll)((long double)a/p*b+)*p);
    return tmp<?tmp+p:tmp;
}
il ll pow(ll a,ll b,ll p)
{
    ll ans=;a%=p;
    while(b)
    {
        if(b&) ans=mul(ans,a,p);
        a=mul(a,a,p);
        b>>=;
    }
    return ans;
}
il bool check(ll a,ll n,ll r,ll s)
{
    ll ans=pow(a,r,n),p=ans;
    for(int i=;i<=s;i++)
    {
        ans=mul(ans,ans,n);
        if(ans== && p!= && p!=n-) return ;
        p=ans;
    }
    if(ans!=) return ;
    return ;
}
il bool MR(ll n)
{
    if(n<=) return ;
    ll r=n-,s=;
    while(r%==) r>>=,s++;
    for(int i=;i<;i++) 
    {
        if(a[i]==n) return ;
        if(check(a[i],n,r,s)) return ;
    }
    return ;
}
il ll rho(ll n,ll c)
{
    ll k=,x=rand()%n,y=x,p=;
    for(ll i=;p==;i++)
    {
        x=(mul(x,x,n)+c)%n;
        p=x>y ? x-y : y-x;
        p=gcd(n,p);
        if(i==k) y=x,k+=k;
    }
    return p;
}
void solve(ll n)
{
    if(n==) return;
    if(MR(n)) {mx=max(mx,n);return;}
    ll t=n;
    while(t==n) t=rho(n,rand()%(n-));
    solve(t);solve(n/t);
}
int main()
{
    n=read();
    while(n--)
    {
        x=read();
        mx=;
        solve(x);
        if(mx==x) puts("Prime");
        else printf("%lld\n",mx);
    }
    return ;
}