P2155 [SDOI2008] 沙拉公主的困惑
求
$$
\sum _ {i = 1} ^ {n!} [gcd(i, m!) = 1]
$$
注意到 $n \ge m$ ，那么 $n !$ 是 $m!$ 的倍数，而 $gcd(a, ka + b) = gcd(a, b)$ ，$\sum _ {i = 1} ^ {m!} [gcd(i, m!)] = \varphi(m!)$ ，那么答案为 $\frac {n !} {m !} \varphi (m !)$ 。
考虑阶乘的欧拉函数如何求，注意到欧拉函数的公式：
$$
\varphi (n) = n\prod _ {p | n} (1 - \frac 1 p)
$$
如果 $m$ 不为质数，那么一定可以被若干个小于 $m$ 的质数整除， $m !$ 和 $(m - 1)!$ 的质因数相同，那么有 $\varphi (m!) = \varphi((m - 1)!) \times m$ ；否则由积性函数的性质有：$\varphi (m!) = \varphi ((m - 1)!) \times \varphi (m)= \varphi ((m - 1)!) \times (m - 1)$ 。
注意到模数太小使得预处理阶乘等于模数后全部为 $0$ ，而实际上还有除法。所以如果 $\left \lfloor \frac n {mod} \right \rfloor > \left \lfloor \frac n {mod} \right \rfloor$ ，那么答案一定为 $0$ 。
查看代码
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
| #include <cstdio>
using namespace std;
template <class Type>
void read(Type &x)
{
char c;
bool flag = false;
while ((c = getchar()) < '0' || c > '9')
c == '-' && (flag = true);
x = c - '0';
while ((c = getchar()) >= '0' && c <= '9')
x = (x << 3) + (x << 1) + c - '0';
if (flag) x = ~x + 1;
}
template <class Type, class ...rest>
void read(Type &x, rest &...y) { read(x), read(y...); }
template <class Type>
void write(Type x)
{
if (x < 0) putchar('-'), x = ~x + 1;
if (x > 9) write(x / 10);
putchar(x % 10 + '0');
}
typedef long long LL;
const int N = 1e7 + 10;
int mod;
bool vis[N];
int cnt, p[N], fact[N], phifact[N];
int binpow (int b, int k = mod - 2)
{
int res = 1;
for (; k; k >>= 1, b = (LL)b * b % mod)
if (k & 1) res = (LL)res * b % mod;
return res;
}
void init()
{
vis[1] = true;
for (int i = 2; i < N; ++i)
{
if (!vis[i]) p[++cnt] = i;
for (int j = 1; j <= cnt && i * p[j] < N; ++j)
{
vis[i * p[j]] = true;
if (i % p[j] == 0) break;
}
}
fact[1] = phifact[1] = 1;
for (int i = 2; i < N; ++i)
{
phifact[i] = (LL)phifact[i - 1] * (vis[i] ? i : i - 1) % mod;
fact[i] = i % mod ? (LL)fact[i - 1] * i % mod : fact[i - 1];
}
}
int main ()
{
int T; read(T, mod); init();
for (int n, m; T; --T)
{
read(n, m);
if (n / mod > m / mod) puts("0");
else write((LL)binpow(fact[m]) * fact[n] % mod * phifact[m] % mod), puts("");
}
return 0;
}
|