[BZOJ2186][SDOI2008]沙拉公主的困惑（数论）

设 f[i] 表示 [1,i!] 的数中与 i! 互质的数的个数。边界为 f[0]=1 。
首先介绍一个性质：当 (a,x)=1 时， (k∗x+a,x)=1 。
当 i 不为质数时， (i−1)! 就已经包含了 i 的所有质因子。所以这时候就变成了求 [1,i!] 中与 (i−1)! 互质的数的个数。可以发现，因为 i!=i∗(i−1)! ，所以可以根据上面的性质推出此时 f[i]=f[i−1]∗i 。
当 i 为质数时就不一样了。因为相对于 (i−1)! ， i! 多了一个质因子 i 。所以在这 f[i−1]∗i 个数中，仍然存在一些数与 i! 的 gcd 大于 1 。但可以发现这些数都与 (i−1)! 互质并且包含质因子 i 。而这些数除以 i 之后，就可以构成 [1,(i−1)!] 中与 (i−1)! 互质的数的集合（因为与 (i−1)! 互质的数除以 i 之后仍然与 (i−1)! 互质）。所以此时 f[i]=f[i−1]∗i−f[i−1]=f[i−1]∗(i−1) 。
到现在，就可以根据上面的性质得出，答案 =f[M]∗N!M! 。对于 N!M! ，可以用逆元计算。
代码：

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
inline int read() {
    int res = 0; bool bo = 0; char c;
    while (((c = getchar()) < '0' || c > '9') && c != '-');
    if (c == '-') bo = 1; else res = c - 48;
    while ((c = getchar()) >= '0' && c <= '9')
        res = (res << 3) + (res << 1) + (c - 48);
    return bo ? ~res + 1 : res;
}
const int N = 1e7;
int T, PYZ, m, n, f[N + 5], fac[N + 5];
bool prm[N + 5];
int qpow(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1) res = (1ll * res * a) % PYZ;
        a = (1ll * a * a) % PYZ;
        b >>= 1;
    }
    return res;
}
int main() {
    T = read(); PYZ = read();
    int i, j; prm[0] = prm[1] = f[0] = fac[0] = 1;
    for (i = 2; i * i <= N; i++) {
        if (prm[i]) continue;
        for (j = i * i; j <= N; j += i)
            prm[j] = 1;
    }
    for (i = 1; i <= N; i++)
        f[i] = 1ll * f[i - 1] * (prm[i] ? i : i - 1) % PYZ,
        fac[i] = 1ll * fac[i - 1] * i % PYZ;
    while (T--) {
        n = read(); m = read();
        int res = 1ll * f[m] * fac[n] % PYZ;
        res = 1ll * res * qpow(fac[m], PYZ - 2) % PYZ;
        printf("%d\n", res);
    }
    return 0;
}