题目
https://www.luogu.com.cn/problem/P4718
思路
真的是阴间卡常模板题
blog
代码
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define ull unsigned long long
using namespace std;
int T;
ll ans,n;
inline ll mul(ll x,ll y,ll p)
{
ll yjy=(ld)x/p*y;
ll aii=(ull)x*y-(ull)yjy*p;
if(aii<0) aii+=p; if(aii>=p) aii-=p;
return aii;
}
inline ll power(ll x,ll t,ll mod)
{
ll b=1;
while(t)
{
if(t&1) b=mul(b,x,mod); x=mul(x,x,mod); t>>=1;
}
return b;
}
inline ll gcd(ll x,ll y)
{
return y==0?x:gcd(y,x%y);
}
bool miller(ll n,int yjy)
{
if(n==2||n==3) return 1;
if(n%2==0||n==1) return 0;
ll d=n-1,s=0;
while(!(d&1)) s++,d>>=1;
while(yjy--)
{
ll a=rand()%(n-3)+2,x=power(a,d,n),y=0;
for(int X=1; X<=s; X++)
{
y=mul(x,x,n);
if(y==1&&x!=1&&x!=n-1)
return 0;
x=y;
}
if(y!=1)
return 0;
}
return 1;
}
ll pollard(ll n)
{
ll x=rand()%(n-1)+1,y=x,i=1,k=2,c=rand()%n,val=1;
while(1)
{
i++;
x=(mul(x,x,n)+c)%n;
val=mul(val,abs(y-x),n);
if(y==x) return n;
if(i==k||i%63==0||i%127==0)
{
ll d=gcd(n,val);
if(1<d&&d<n) return d;
if(i==k) y=x,k<<=1;
}
}
}
void find(ll n)
{
if(n==1) return;
if(ans>=n) return;
if(miller(n,20))
{
ans=max(ans,n); return;
}
ll p=n;
while(p==n)
p=pollard(p);
find(p); find(n/p);
}
int main()
{
srand(time(NULL));
scanf("%d",&T);
while(T--)
{
ans=0;
scanf("%lld",&n);
find(n);
if(ans==n) printf("Prime\n");
else printf("%lld\n",ans);
}
}