[BZOJ 1951][SDOI 2010] 古代猪文

题目大意

已知远古时期猪文文字总个数为 \(N\),某一朝代流传的文字是远古时期的 \(k\) 分之一,其中 \(k\)\(N\) 的一个正约数(可以是 \(1\)\(N\)),不过具体是哪 \(k\) 分之一,以及 \(k\) 是多少并不知道。考虑到所有可能的 \(k\),显然当 \(k\) 等于某个定值时,该朝的猪文文字个数为 \(\frac{N}k\)。如果所有可能的\(k\)的所有情况数加起来为 \(P\) 的话,那么研究古代文字的代价将会是 \(G^P\)。 现在他想知道猪王国研究古代文字的代价是多少。答案对 \(999911659\) 取模。

输入 \(N、G\)

\(N, G \leqslant 1,000,000,000\)

题目链接

BZOJ 1951

CodeVS 1830

题解

首先,显然题目是让我们求这么一个东西:

\[G^{ \sum_{k | N} \binom{N}{k}} \bmod \; 999911659\]

好吧,这个东西的指数一看就很大,怎么办呢?由欧拉定理,我们易得:

\[a^{b} \equiv a^{b \bmod \; \varphi(p)} (\bmod \; p), \; \gcd(a, \ p) = 1\]

另外,我们有:

\[a^{b} \equiv (a \bmod \; p)^{b} \; (\bmod \; p)\]

不过,当 \(G = P\)\(\varphi(P) \ | \ b\) 时,显然有答案为 \(0\),但用以上二式会得到 \(0^0 = 1\),故我们应当适当改造一下式子一,把指数改为 \(b \bmod \; \varphi(p) + \varphi(p)\) 即可。(根据 Po 姐的博客,我们知道还真有这么一个点来卡这个。。。)

在此题中,显然有 \(\varphi(p) = 999911658\),显然不是质数,因此我们要对其进行质因数分解,用中国剩余定理合并答案。(因为不是质数,所以在计算组合数时可能会不存在逆元)分解结果如下:

\[999911658 = 2 \times3 \times 4679 \times 35617\]

(在 Linux 下,我们可以进入终端,在终端中输入 factor 999911658即可进行质因数分解)

然后是中国剩余定理合并答案,其内容是:

已知 \(x \equiv a_i \ (\bmod \; m_i), \ gcd(m_1, m_2, \dots, m_n) = 1\),则 \(x\) 在模 \(M\)\(M\) 的含义见下)意义下有唯一解,且可由以下方法求得:

\[M = \prod m_i, \ M_i = \frac{M}{m_i}, \ t_i = M_i^{-1} (\bmod \; m_i)\]

\[x = \sum a_i t_i M_i \bmod \; M\]

你以为这就完了?计算组合数时,\(N\)\(k\) 也很大,需要用到 Lucas 定理:

\[\binom{sp + a}{tq + b} = \binom{p}{q} \ \binom{a}{b}​\]

然后直接算就行了。。。一道题,考了三个数论定理,还有一个坑。。。

代码

代码注释中的英文看看就好。。。

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <cstdio>
// #define DBG
typedef long long ll;
const ll MOD = 999911659;
const ll PHI_MOD = 999911658;
ll divisorOfP[4] = {2, 3, 4679, 35617};
ll fac[4][35617], inv[4][35617];
ll ans[5];
void linearShaker(ll p, ll fac[], ll inv[]) {
fac[0] = 1;
for (int i = 1; i < p; i++) fac[i] = fac[i - 1] * i % p;
inv[1] = 1;
for (int i = 2; i < p; i++) inv[i] = (p - p / i) * inv[p % i] % p;
inv[0] = 1;
for (int i = 1; i <= p; i++) inv[i] = inv[i] * inv[i - 1] % p;
}
ll n, g;
ll combin(ll n, ll m, ll p, ll fac[], ll inv[]) {
if (n < m) return 0;
if (n < p && m < p) return fac[n] * inv[m] % p * inv[n - m] % p;
//Lucas Theorem
//\binom{sp + a}{tq + b} = \binom{a}{b} * \binom{p}{q}
return combin(n % p, m % p, p, fac, inv) * combin(n / p, m / p, p, fac, inv) % p;
}
void calc(ll x) {
#ifdef DBG
printf("calc(%lld)\n", x);
#endif
for (int i = 0; i < 4; i++) {
ans[i] += combin(n, x, divisorOfP[i], fac[i], inv[i]);
ans[i] %= divisorOfP[i];
}
}
ll pow(ll a, ll n, ll p) {
ll res = 1;
for (; n; n >>= 1, a = a * a % p) if (n & 1) res = res * a % p;
return res;
}
ll calcInv(ll n, ll p) {
return pow(n, p - 2, p);
}
//Chinese Remainder Theorem(CRT)
//known : x mod m_i = a_i
//calc x
//def M = \prod_{i} m_i, M_i = M / m_i, t_i * M_i = 1 (mod m_i)
//when mod M, there is only one root of the equation
//x = \sum_{i} a_i * t_i * M_i
ll ChineseRemainderTheorem() {
ll res = 0;
for (int i = 0; i < 4; i++) {
ll x = calcInv(PHI_MOD / divisorOfP[i], divisorOfP[i]);
ll temp = (x % PHI_MOD * (PHI_MOD / divisorOfP[i]) % PHI_MOD + PHI_MOD) % PHI_MOD;
res += temp * ans[i] % PHI_MOD;
res %= PHI_MOD;
}
return res;
}
ll pow(ll a, ll n) {
ll res = 1;
for (; n; n >>= 1, a = a * a % MOD) if (n & 1) res = res * a % MOD;
return res;
}
int main() {
for (int i = 0; i < 4; i++) linearShaker(divisorOfP[i], fac[i], inv[i]);
scanf("%lld %lld", &n, &g);
for (int i = 1; i * i <= n; i++) {
if (n % i == 0) {
calc(i);
if (i * i != n) calc(n / i);
}
}
ans[4] = ChineseRemainderTheorem();
#ifdef DBG
for (int i = 0; i < 4; i++) printf("a_%d = %lld\n", i + 1, ans[i]);
printf("\\sum_{d | n} \\binom{N}{k} = %lld\n", ans[4]);
#endif
//Euler Theorem
//a^b mod p = a^(b mod phi(p)) mod p, gcd(a, p) = 1, a, p != 0
//(come from : a^phi(p) mod p = 1, gcd(a, p) = 1, a, p != 0)
//to deal with the situation when a = 0, use a^(b^phi(p) + phi(p)) mod p
ans[4] = pow(g % MOD, ans[4] + PHI_MOD);
printf("%lld\n", ans[4]);
return 0;
}