TLE 95Pts 最慢点4.09S求调

#include <bits/stdc++.h>

using namespace std;

const int N=1e2+10;
vector <long long  > v;
long long t,n,tot,p[N],vis[N],c;
 
__int128 pw(__int128 a,__int128 b,__int128 Mod) 
{
	long long res=1;
	while(b)
	{
		if(b&1) res=res*a%Mod;
		a=a*a%Mod;
		b>>=1;
	}
	return res;
}

int miller_rabin(long long k)
{
	if(k<=100) return 1-vis[k];
	long long r=k-1,s=0;
	while((r&1)==0) r>>=1,s++;
	for(int i=1;i<=12;i++)
	{
		__int128 a=p[i]; 
		a=pw(a,r,k);
		for(int i=0;i<s;i++) 
		{
			if(a*a%k==1&&(a!=1&&a!=k-1)) return 0;
			a=a*a%k; 
		}
		if(a!=1) return 0;
	}
	return 1;
}

long long f(__int128 x,long long Mod)
{
	return (x*x+c)%Mod;
}

void solve(long long k)
{
	if(k==4) 
	{
		v.push_back(2);
		v.push_back(2);
		return ;
	} 
	if(miller_rabin(k)==1)
	{
		v.push_back(k);
		return ;
	}
	c=1ll*rand()*rand()*rand();
	long long i=f(0,k),j=f(f(0,k),k);
	while(i!=j) 
	{
        long long rs=__gcd(abs(i-j),k);
		if(rs!=1) 
		{
			solve(rs);
			solve(k/rs); 
			return ;
		}
		i=f(i,k),j=f(f(j,k),k);
	}
	solve(k);
	return ;
}

int main()
{
	for(int i=2;i<=N-10;i++) 
	{
		if(vis[i]==0)
		{
			p[++tot]=i;
			for(int j=2*i;j<=N-10;j+=i) vis[j]=1;
		}
	}
	scanf("%lld",&t);
	while(t--)
	{
		scanf("%lld",&n);
		v.clear();
		solve(n);
		sort(v.begin(),v.end());
		if(v.size()==1) printf("Prime\n"); 
		else printf("%lld\n",v[v.size()-1]);
//		for(long long k:v) printf("%lld ",k);
//		printf("\n"); 
	} 
	return 0;
}