已经使用以下卡常

1. 输入输出优化
2. 快速乘法
3. 减少求gcd的次数
4. fac函数的简单剪枝

#include<iostream>
#include<cmath>
#include<algorithm>
#include<stdlib.h>
#include<ctime>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef __int128_t lll;
ll max_factor=0;
ll Test[12]={2,3,5,7,11,13,17,19,23,29,31,37};
inline ll gcd(ll a,ll b){
    if(!b) return a;
    return gcd(b,a%b);
}
inline ll mabs(ll x){
    return x>=0?x:-x;
}
inline ll qmul(ll a,ll b,ll p){
    ll res=a*b-ll((long double)a/p*b+1e-8)*p;
    return res<0?res+p:res;
}
inline ll qpow(ll a,ll b,ll p){
    ll re=1;
    while(b){
        if(b%2){
            re=qmul(re,a,p);
        }
        b/=2;
        a=qmul(a,a,p);
    }
    return re;
}
bool MR(ll N){
    if(N==1) return 0;
    int t=N-1,k=0;
    while(!(t&1)) ++k,t>>=1;
    for(int i=0;i<12;++i){
        if(N==Test[i]) return 1;
        ll a=qpow(Test[i],t,N), nxt=a;
        for(int j=1;j<=k;++j){
            nxt=qmul(a,a,N);
            if(nxt==1&&a!=1&&a!=N-1) return 0;
            a=nxt;
        }
        if(a!=1) return 0;
    }
    return 1;
}
ll PR(ll N){
    if(N==4) return 2;
    if(MR(N)) return N;
    while(1){
        ll c=1ll*rand()%(N-1)+1;
        //cout<<c<<endl;
        auto f=[=] (ll x) {return ((lll)x*x+c)%N;};
        ll t=0,r=0,p=1,q;
        do{
            for(int j=1;j<=128;j<<=1)
                for(int i=0;i<j;++i){
                    t=f(t),r=f(f(r));
                    if(t==r||(q=(lll)p*mabs(t-r)%N)==0) break;
                    p=q;
                }        
            ll d=gcd(p,N);
            if(d>1) return d;
        }while(t!=r);
    }
}
void fac(ll x){
    if(x<=max_factor||x<2) return ;
    ll p=PR(x);
    if(p==x){
        max_factor=max_factor>x?max_factor:x;
        return;
    }
    while(x%p==0) x/=p;
    fac(x),fac(p);
}
int main()
{
    //freopen("test.in","r",stdin);
    //freopen("test.out","w",stdout);
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    srand((unsigned)time(NULL));
    int T; cin>>T;
    ll n;
    while(T--){
        max_factor=0;
        cin>>n;
        fac(n);
        if(max_factor==n) cout<<"Prime"<<endl;
        else cout<<max_factor<<endl;
    } 
    return 0;
}

不希望通过打一定范围的质数表的方式过掉此题，求助。