题意:给出质数P(1e9~1e14) ，求出比P小的最大质数Q，输出Q!modP

分析:我是直接从P-1递减判断是否为质数，虽然过了但是很低效，更好的做法是米勒测试，我不会所以就不写了。求出Q之后，就要算Q!modp。直接算显然超时，注意到P为质数，所以想到威尔逊定理 : (p-1)!-1modp当且仅当p为质数时成立，加个模数-1变成P-1。所以倒着算Q!=(P-1)! / [ (p-1) * (p-2) * (p-3)..... * (a+1) ]。中间除法取模要求一下逆元可用费马小定理或ex_gcd。wa了几次后发现题目给的范围可能爆unsignedlonglong，所以这道题的乘法需要使用快速乘，但是听说G++可以int128，没去试，但应该是可行的

代码: 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e7 + 3;
bool f(ll n)
{
    for(ll i=2;i*i<=n;i++)
        if(n%i==0) return false;
    return true;
}
ll mul(ll a,ll b,ll mod)
{
    ll ans=0;
    while(b)
    {
        if(b&1)    ans=(ans+a)%mod;
        a=(a<<1)%mod;
        b>>=1;
    }
    return ans;
}
ll ksm(ll a,ll b,ll mod)
{
    ll ans=1;
    while(b)
    {
        if(b&1) ans=mul(ans,a,mod);
        a=mul(a,a,mod);
        b>>=1;
    }
    return ans;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        ll flag,a,b;
        cin>>b;
        for(ll i=b-1;i>=0;i--) 
            if(f(i)) 
            {
                a=i;break;
            }
        ll ans=b-1;
        for(ll i=b-1;i>=a+1;i--) ans=mul(ans,ksm(i,b-2,b),b);
        printf("%lld\n",ans);
    }
    return 0;
}