$$ans = \frac{n!}{m!}\times \phi{m!}$$ $$令 p_1,p_2,\dots,p_m 为 (m!) 的质因子（每种一个）$$ $$则 \phi{(m!)} = m!\times \frac{p_1-1}{p_1}\times \frac{p_2-1}{p_2}\times \cdots \times \frac{p_m-1}{p_m} $$$$ans = \frac{n!}{m!}\times m!\times \frac{p_1-1}{p_1}\times \frac{p_2-1}{p_2}\times \cdots \times \frac{p_m-1}{p_m} $$$$= n!\times \frac{p_1-1}{p_1}\times \frac{p_2-1}{p_2}\times \cdots \times \frac{p_m-1}{p_m} $$

于是基本做法就是预处理：

• fact[i] = i!
• f[i] = (p1-1)*inv[p1] * (p2-1)*inv[p2] ... 右边为i! 的所有质因子，实际上就是 1~i 中的所有质数。

然后就可以得到答案。

这种做法有一个小瑕疵，就是当 $m>=R(模数)$ 的时候，

$$ans = \frac{n!}{m!}\times m!\times \frac{p_1-1}{p_1}\times \frac{p_2-1}{p_2}\times \cdots \times \frac{p_m-1}{p_m} $$

此时 $n!$ 里面的 $R$ 可以和分母的 $m!$ 里的 $R$ 约掉，右边 $m!$ 里的 $R$ 可以和右边分母的某个等于 $R$ 的 $p$ 约掉。

所以此时要预处理：

• fact[i] = i!/R（跳过 R 的阶乘）。
• f[i] = R * (p1-1)*inv[p1] * (p2-1)*inv[p2] ...（实际上就是某个乘以 inv[R] 跳过不做）

反映到代码中就是：

fact[0] = factR[0] = 1;
for (long long i = 1; i <= 10000000; i++)
{
    if (i == R)
        fact[i] = fact[i - 1]; // 跳过R
    else
        fact[i] = (i * fact[i - 1]) % R;
    factR[i] = (i * factR[i - 1]) % R;
}

与

f[0] = 1;
for (int i = 1; i <= 10000000; i++)
{
    if (!vis[i])
        f[i] = (long long)f[i - 1] * (i - 1) % R;
    else
        f[i] = f[i - 1];
    if (!vis[i] && i != R)
        f[i] = (long long)f[i] * inv[i] % R; // 跳过 R
}

---

完整代码

#include <bits/stdc++.h>
using namespace std;
int T, R;
int n, m;
int fact[11234567];
int factR[11234567];
int inv[11234567];
int f[11234567];
const int MAXN = 11234567;
bool vis[MAXN];
int ptot, pri[MAXN];
void init()
{
    vis[0] = vis[1] = 1;
    for (int i = 2; i < MAXN; ++i)
    {
        if (!vis[i])
            pri[ptot++] = i;
        for (int j = 0; j < ptot; ++j)
        {
            if (1ll * i * pri[j] >= MAXN)
                break;
            vis[i * pri[j]] = 1;
            if (i % pri[j] == 0)
                break;
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> T >> R;
    fact[0] = factR[0] = 1;
    for (long long i = 1; i <= 10000000; i++)
    {
        if (i == R)
            fact[i] = fact[i - 1]; // 跳过R
        else
            fact[i] = (i * fact[i - 1]) % R;
        factR[i] = (i * factR[i - 1]) % R;
    }
    inv[1] = 1;
    for (long long i = 2; i <= 10000000; i++)
        inv[i] = (-R / i + R) * inv[R % i] % R;
    init();
    f[0] = 1;
    for (int i = 1; i <= 10000000; i++)
    {
        if (!vis[i])
            f[i] = (long long)f[i - 1] * (i - 1) % R;
        else
            f[i] = f[i - 1];
        if (!vis[i] && i != R)
            f[i] = (long long)f[i] * inv[i] % R; // 跳过 R
    }
    while (T--)
    {
        cin >> n >> m;
        if (m >= R)
            cout << (long long)fact[n] * f[m] % R << "\n";
        else
            cout << (long long)factR[n] * f[m] % R << "\n";
    }
    return 0;
}