101 lines
1.7 KiB
C++
101 lines
1.7 KiB
C++
#include<cstdio>
|
|
#include<algorithm>
|
|
using namespace std;
|
|
typedef long long LL;
|
|
const int ps[]={2,3,5,7,11,13,17,19,23,29,31,37};
|
|
const int pcnt=sizeof(ps)/sizeof(int);
|
|
inline LL mt(LL a,LL b,LL m)
|
|
{
|
|
LL d=((long double)a/m*b+1e-8);
|
|
LL r=a*b-d*m;
|
|
return r<0?r+m:r;
|
|
}
|
|
inline LL mpow(LL a,LL b,LL m)
|
|
{
|
|
LL res=1;
|
|
for(;b;b>>=1,a=mt(a,a,m)) if(b&1) res=mt(res,a,m);
|
|
return res;
|
|
}
|
|
inline LL gcd(LL a,LL b)
|
|
{
|
|
if(!a||!b) return a+b;
|
|
int t=__builtin_ctzll(a|b);
|
|
a>>=__builtin_ctzll(a);
|
|
do
|
|
{
|
|
b>>=__builtin_ctzll(b);
|
|
if(a>b) { LL t=b; b=a; a=t; }
|
|
b-=a;
|
|
}
|
|
while(b!=0);
|
|
return a<<t;
|
|
}
|
|
inline int isp(LL n)
|
|
{
|
|
if(n==1) return 0;
|
|
if(n==2||n==3||n==5) return 1;
|
|
if(!(n&1)||(n%3==0)||(n%5==0)) return 0;
|
|
LL m=n-1; int k=0;
|
|
while(!(m&1)) m>>=1,++k;
|
|
for(int i=0;i<pcnt&&ps[i]<n;++i)
|
|
{
|
|
LL x=mpow(ps[i],m,n),y=x;
|
|
for(int i=0;i<k;i++)
|
|
{
|
|
x=mt(x,x,n);
|
|
if(x==1&&y!=1&&y!=n-1) return 0;
|
|
y=x;
|
|
}
|
|
if(x!=1) return 0;
|
|
}
|
|
return 1;
|
|
}
|
|
LL f[105],cnt;
|
|
inline LL nxt(LL x,LL n,LL a)
|
|
{
|
|
x=mt(x,x,n)+a;
|
|
return x<n?x:x-n;
|
|
}
|
|
const int M=(1<<7)-1;
|
|
inline LL rho(LL n)
|
|
{
|
|
if(n%2==0) return 2; if(n%3==0) return 3;
|
|
LL x=0,y=0,t=1,q=1,a=(rand()%(n-1))+1;
|
|
for(int k=2;true;k<<=1,y=x,q=1)
|
|
{
|
|
for(int i=1;i<k;++i)
|
|
{
|
|
x=nxt(x,n,a);
|
|
q=mt(q,abs(x-y),n);
|
|
if(!(i&M))
|
|
{
|
|
t=gcd(q,n);
|
|
if(t>1) break;
|
|
}
|
|
}
|
|
if(t>1||(t=gcd(q,n))>1) break;
|
|
}
|
|
if(t==n) for(t=1;t==n;t=gcd(abs((x=nxt(x,n,a))-y),n));
|
|
return t;
|
|
}
|
|
void solve(LL n)
|
|
{
|
|
if(n==1) return;
|
|
if(isp(n)) { f[cnt++]=n; return; }
|
|
LL t=n; while(t==n) t=rho(n);
|
|
solve(t); solve(n/t);
|
|
}
|
|
int main()
|
|
{
|
|
int T; LL n;
|
|
scanf("%d",&T);
|
|
while(T-->0)
|
|
{
|
|
scanf("%lld",&n);
|
|
cnt=0; solve(n); sort(f,f+cnt);
|
|
if(cnt==1) puts("Prime");
|
|
else printf("%lld\n",f[cnt-1]);
|
|
}
|
|
return 0;
|
|
}
|