【BZOJ3667】Rabin

【BZOJ3667】Rabin

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[]={2,3,5,7,11,13,17,19,23,29};
il ll read()
{ll x=0,f=1;char c=getchar();while(c<'0' || c>'9') {if(c=='-') f=-1;c=getchar();}while(c<='9' && c>='0') {x=x*10+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+1e-8)*p);return tmp<0?tmp+p:tmp;
}
il ll pow(ll a,ll b,ll p)
{ll ans=1;a%=p;while(b){if(b&1) ans=mul(ans,a,p);a=mul(a,a,p);b>>=1;}return ans;
}
il bool check(ll a,ll n,ll r,ll s)
{ll ans=pow(a,r,n),p=ans;for(int i=1;i<=s;i++){ans=mul(ans,ans,n);if(ans==1 && p!=1 && p!=n-1) return 1;p=ans;}if(ans!=1) return 1;return 0;
}
il bool MR(ll n)
{if(n<=1) return 0;ll r=n-1,s=0;while(r%2==0) r>>=1,s++;for(int i=0;i<10;i++) {if(a[i]==n) return 1;if(check(a[i],n,r,s)) return 0;}return 1;
}
il ll rho(ll n,ll c)
{ll k=2,x=rand()%n,y=x,p=1;for(ll i=1;p==1;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==1) return;if(MR(n)) {mx=max(mx,n);return;}ll t=n;while(t==n) t=rho(n,rand()%(n-1));solve(t);solve(n/t);
}
int main()
{n=read();while(n--){x=read();mx=0;solve(x);if(mx==x) puts("Prime");else printf("%lldn",mx);}return 0;
}