Fansblog
解题思路
Q! % P = (P-1)!/(P-1)...(Q-1) % P。
因为P是质数，根据威尔逊定理，(P-1)!%P=P-1。所以答案就是(P-1)((P-1)...*(Q-1)的逆元)%P。数据很大，用__int128。
代码如下
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
inline int read(){
int res = 0, w = 0; char ch = 0;
while(!isdigit(ch)){
w |= ch == '-', ch = getchar();
}
while(isdigit(ch)){
res = (res << 3) + (res << 1) + (ch ^ 48);
ch = getchar();
}
return w ? -res : res;
}
template <typename A, typename B, typename C>
inline A fpow(A x, B p, C lyd){
A ans = 1;
for(; p; p >>= 1, x = 1LL * x * x % lyd)if(p & 1)ans = 1LL * x * ans % lyd;
return ans % lyd;
}
__int128 get_inv(__int128 b, __int128 mod){
return fpow(b, mod - 2, mod);
}
int main()
{
int t;
t = read();
while(t --){
ll p;
scanf("%lld", &p);
__int128 ans = 1;
for(ll i = p - 1; i >= 2; i --){
bool flg = true;
for(ll j = 2; j <= sqrt(i); j ++){
if(i % j == 0){
flg = false;
break;
}
}
if(flg)
break;
ans = (ans * i) % p;
//cout << ans << endl;
}
//cout << ans << endl;
ll k = get_inv(ans, p) % p * (p - 1) % p;
printf("%lld
", k);
}
return 0;
}