题目链接：BZOJ - 2186
题目分析
题目要求出 [1, n!] 中有多少数与 m! 互质。(m <= n)
那么在 [1, m!] 中有 phi(m!) 个数与 m! 互质,如果一个数 x 与 m! 互质，即 gcd(m!, x) = 1，
那么 gcd(m!, m! + x) = 1, gcd(m!, m! * 2 + x) = 1, 即 x + k * m! 都与 m! 互质。
这样就很明确了，[1, n!] 中与 m! 互质的数有 phi(m!) * n! / m! 个。
怎么求 phi(m!) 呢？我们知道，一个数 x 如果包含 p^a ，那么 phi(x) 中就含有 p^(a-1) * (p - 1)。
也就是说， phi(x) = x / pi * (pi - 1) ， pi 是枚举 x 包含的质数。那么 m! 包含的质数就是 [1, m] 的质数，线性筛就可以了。
最后化简 Ans = n! / pi * (pi - 1) 。pi 是 [1, m] 的质数。
代码
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm> using namespace std; typedef long long LL; const int MaxN = 10000000 + 5, MN = 10000000; int T, Mod, n, m, Top, Ans;
int Prime[MaxN], Fac[MaxN], Inv[MaxN], Pi[MaxN]; bool isPrime[MaxN]; void Prepare()
{
for (int i = 1; i <= MN; ++i) isPrime[i] = true;
isPrime[1] = false;
for (int i = 2; i <= MN; ++i)
{
if (isPrime[i]) Prime[++Top] = i;
for (int j = 1; j <= Top && i * Prime[j] <= MN; ++j)
{
isPrime[i * Prime[j]] = false;
if (i % Prime[j] == 0) break;
}
}
Inv[1] = 1;
int q, r;
for (int i = 2; i <= MN; ++i)
{
q = Mod / i;
r = Mod % i;
Inv[i] = (int)((LL)(Mod - q) * (LL)Inv[r] % Mod);
}
Fac[0] = Pi[0] = 1;
for (int i = 1; i <= MN; ++i)
{
Fac[i] = (int)((LL)Fac[i - 1] * (LL)i % Mod);
if (isPrime[i]) Pi[i] = (int)((LL)Pi[i - 1] * (LL)Inv[i] % Mod * (LL)(i - 1) % Mod);
else Pi[i] = Pi[i - 1];
}
} int main()
{
scanf("%d%d", &T, &Mod);
Prepare();
for (int Case = 1; Case <= T; ++Case)
{
scanf("%d%d", &n, &m);
Ans = (int)((LL)Fac[n] * (LL)Pi[m] % Mod);
printf("%d\n", Ans);
}
return 0;
}