题意在这里。
为了解决本题，需要知道的概念有欧拉函数和乘法逆元。
欧拉函数简单来说就是f(m)是所有比它小的数中与它互质的数的个数（包括1）。求欧拉函数必须要知道的性质是f(m)=(p1-1)/p1*…(pm-1)/pm. 其中p1至pm表示其所有质因数（各不相同）。
同时我们还需要知道一个数如果与n互质，那么它加上n也仍然与n互质。
因此我们的答案就是phi(m!) * (n!/m!) % p ——> 因为m！的所有质因子其实就是m以内的所有质数，
答案化为：n! * 连乘(Pi-1)/Pi
而模意义下的除法不可以直接上下取模，而是要把分母转换成乘上它的逆元的形式。
逆元的意思就是ax = 1 （mod b）那么x就是a在模b意义下的逆元。
这里有一个线性求逆元的方法：
inv[i] = (M - M/i) * inv[M%i] mod M
证明在这里
之后就非常好做啦！连乘的时候判断是否是质数。并且一直取模就好。
代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
using namespace std;
long long T,R;
const int N = 10000000;
bool isprime[N+7];
long long prime[100000+7],fac[N+7],inv[N+7],ans[N+7];
int n,m;
int tot = 0;
void solve()
{
memset(isprime,1,sizeof isprime);
isprime[1] = false;
for (int i = 1; i <= N; i++)
{
if(isprime[i]) prime[++tot] = i;
for (int j = 1; j <= tot && prime[j]*i <= N; j++)
{
isprime[i*prime[j]] = false;
if(i % prime[j] == 0) break;
}
}
fac[1] = 1;
for (int i = 2; i <= N; i++) fac[i] = fac[i - 1] * i % R;
inv[1] = 1;
for (int i = 2; i <= N && i < R; i++) inv[i] = (R - R/i) * inv[R % i] % R;
ans[1] = 1;
for (int i = 2; i <= N; i++)
{
//cout<<i<<endl;
if(isprime[i]) ans[i] = ans[i - 1] * (i - 1)%R * inv[i % R] % R;
else ans[i] = ans[i - 1];
}
}
int main()
{
scanf("%lld%lld",&T,&R);
solve();
while(T--)
{
scanf("%d%d",&n,&m);
// cout<<fac[n]<<" "<<ans[m]<<endl;
long long res = fac[n] * ans[m] % R;
printf("%lld\n",res);
}
return 0;
}
参考：这里