题意:
求 \(Q!\) % P, Q 是最大的那个小于 P 的质数 (1e9 < P < 1e14, P 为质数)。
思路:
注意用龟速乘,会爆longlong.
AC代码:
// -----------------
//#pragma GCC optimize(2)
#include <iostream>
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(0);
#define endl '\n'
#define int long long
using namespace std;
const int N = 1e7 + 7;
int p,q,mod;
int cnt,pr[N];
bool st[N];
void initpr(int n) //预处理1e7内的质数用来判素数,大概6e5个
{
for(int i = 2; i <= n; i ++)
{
if(!st[i]) pr[ ++ cnt] = i;
for(int j = 1; j <= cnt && i * pr[j] <= n; j ++)
{
st[i * pr[j]] = 1;
if(i % pr[j] == 0 ) break;
}
}
}
bool pd(int x) // 判素数
{
for(int i = 1; i <= cnt && pr[i] * pr[i] <= x; i ++)
{
if(x % pr[i] == 0) return false;
}
return true;
}
int mul(int a, int b) // 龟速乘
{
if(b < 0) a = -a, b = -b;
int res = 0;
while(b)
{
if(b & 1) res = (res + a) % mod;
a = (a + a) % mod;
b >>= 1;
}
return res;
}
int ksm(int a, int b)
{
int res = 1;
while(b)
{
if(b & 1) res = mul(res, a);
a = mul(a, a);
b >>= 1;
}
return res;
}
void solve()
{
cin >> p;
mod = p;
q = p - 1;
int ans = p - 1;
while(pd(q) == false) q --; // 暴力判,素数距离不超过300
q ++;
while(q < p) ans = mul(ans,ksm(q, mod - 2)), q ++; //
cout << ans << endl;
}
signed main()
{
IOS initpr(N - 7);
int T = 1;
cin >> T;
while(T --) { solve(); }
return 0;
}