「一本通 6.6 例 4」古代猪文

形式化题目

给定 $N, G$ ，其中 $k$ 取遍 $N$ 的全部正约数，每个 $k$ 对应 $\dfrac Nk$ 种保留字数的方案 $\dbinom{N}{N/k}$ 。令

P = \sum_{k \mid N} \binom{N}{N/k} = \sum_{k \mid N} \binom{N}{k},

求 $G^{P} \bmod 999911659$ 。约束为 $1 \leqslant G \leqslant 10^9$ ， $1 \leqslant N \leqslant 10^9$ 。

（题面描述里出现过“ $9999116594$ ”，但输出格式段与样例都指向模数 $999911659$ ，且只有 $999911659$ 是质数、才使下文的中国剩余定理分解成立，故以 $999911659$ 为准。）

样例 $N = 4$ 的约数是 $1, 2, 4$ ，对应方案数如下：

$k$	保留字数 $N/k$	方案数 $\binom{N}{N/k}$
1	4	1
2	2	6
4	1	4

所以 $P = 1 + 6 + 4 = 11$ ，答案 $2^{11} = 2048$ ，与样例一致。注意两种求和写法 $\sum_{k\mid N}\binom{N}{N/k}$ 与 $\sum_{k\mid N}\binom Nk$ 完全等价，因为 $k \mapsto N/k$ 是约数集合上的一个置换。

正解

思路

第一步：先解决"能不能算"。 $N$ 可以到 $10^9$ ，此时 $\binom{N}{N/2}$ 约有 $3 \times 10^8$ 位十进制数字， $P$ 大到无法存储， $G^{P}$ 更无从下手。但题目只要答案模 $999911659$ ，而这个模数是质数。于是当 $\gcd(G, 999911659) = 1$ 时费马小定理给出

G^{999911658} \equiv 1 \pmod{999911659} \;\Longrightarrow\; G^{P} \equiv G^{\,P \bmod 999911658} \pmod{999911659}.

任务立刻变成：求 $P \bmod 999911658$ ，其中 $P = \sum_{k \mid N}\binom Nk$ 。 （ $G$ 是模数的倍数时降幂不成立，单独返回 $0$ 即可。）

第二步：把模数减一拆开。 试除分解得到

999911658 = 2 \times 3 \times 4679 \times 35617,

四个因子都是质数。四者两两互素，所以只要分别在四个模数下求出 $P$ ，中国剩余定理就能唯一还原 $P \bmod 999911658$ 。这一步把一个"模数接近 $10^9$ "的大问题，换成了四个"模数不超过 $35617$ "的小问题。

第三步：用小质数模数反而更省事。 大数取模的组合数通常要按 $\binom nk = \dfrac{n!}{k!\,(n-k)!}$ 写作阶乘并处理其中的 $p$ 因子（即扩展 Lucas）。但 Lucas 定理的形式是

\binom{n}{k} \equiv \prod_{i \geqslant 0} \binom{n_i}{k_i} \pmod p, \qquad n = \sum_i n_i p^i,\quad k = \sum_i k_i p^i .

把 $n, k$ 反复整除 $p$ 就能逐位取出 $n_i, k_i$ 。某一位上 $k_i > n_i$ 时该位为 $0$ ，整个乘积就是 $0$ ——这恰好覆盖了 $p \mid \binom nk$ 的情形。所以小模数不需要任何特殊处理，逐位相乘即可。

用样例 $N = 4$ （真值 $P = 11$ ）在 $p = 2$ 下验证这一点：

$k$	$k$ 的 $2$ 进制	Lucas 逐位乘积	值
1	$001$	$\binom{0}{1}$ （第 $0$ 位超出）	$0$
2	$010$	$\binom{0}{0} \cdot \binom{0}{1}$ （第 $1$ 位超出）	$0$
4	$100$	$\binom{0}{0} \cdot \binom{0}{0} \cdot \binom{1}{1}$	$1$
		合计 $P \bmod 2$	$1$

$11 \bmod 2 = 1$ 对上了。注意不能偷懒只取一次低位： $\binom 42 = 6 \equiv 0 \pmod 2$ ，而 $\binom{4 \bmod 2}{2 \bmod 2} = \binom 00 = 1$ ；真正的 Lucas 是每一位都乘，第 $1$ 位上 $k_1 = 1 > n_1 = 0$ 令乘积归零，这才和 $6 \equiv 0 \pmod 2$ 相符。

第四步：合并四个余数。 设第 $i$ 个模数的余数为 $r_i$ ，逐项增量合并：维护"已合并好的部分" $r \bmod M$ ，新模数 $p$ 到来时取

t = (r_i - r) \cdot M^{-1} \bmod p, \qquad r \leftarrow r + t\,M,\quad M \leftarrow M \cdot p .

$M$ 始终是若干不同素因子之积，与下一个 $p$ 互素，逆元必然存在。四项合并完 $M = 999911658$ ，得到的 $r$ 就是需要的指数，答案即 pow(G, r, 999911659)。

正确性上有四点要把住。

约数用试除配对枚举， $d$ 与 $N/d$ 各收一次，但完全平方数时中间那个约数只能记一次，否则 $P$ 会被多加一遍。
四个模数互素，所以 CRT 的还原在 $[0, 999911658)$ 内唯一，求出的指数不多不少。
$G \equiv 0 \pmod{999911659}$ 是费马降幂唯一失效的情形，要单独输出 $0$ 。
Lucas 内的 $\binom{n_i}{k_i}$ 用阶乘表与逆元表 $O(1)$ 查询；逆元表由 pow(fact[p-1], -1, p) 求出末项后倒推，避免对 $p$ 个数逐个求逆元。

代码

Python 版：

python

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
85
86
87
88#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 00:09
# update_at: 2026-10-01 00:22

import sys
from functools import cache
from math import isqrt

MOD = 999911659
# 指数 P 只需 mod (MOD-1)（费马小定理；G 不是 MOD 的倍数时成立）。
# MOD-1 = 999911658 = 2 × 3 × 4679 × 35617，四个两两互素的素因子，
# 所以每个素因子下用 Lucas 定理求 P，再用中国剩余定理合并回 mod (MOD-1)。
CRT_MODS = (2, 3, 4679, 35617)


def divisors(n: int) -> list[int]:
    """n 的全部正约数，按从小到大返回。"""
    low, high = [], []
    for d in range(1, isqrt(n) + 1):
        if n % d == 0:
            low.append(d)
            if d != n // d:  # 完全平方数时中间那个约数只算一次
                high.append(n // d)
    return low + high[::-1]


@cache
def pascal_row(p: int) -> tuple[tuple[int, ...], tuple[int, ...]]:
    """模 p 意义下的阶乘表与阶乘逆元表，用来 O(1) 查 C(a, b) mod p（a, b < p）。"""
    fact = [1] * p
    for i in range(1, p):
        fact[i] = fact[i - 1] * i % p
    inv = [1] * p
    inv[p - 1] = pow(fact[p - 1], -1, p)  # p 是质数且 p ∤ (p-1)!，末项可逆
    for i in range(p - 1, 0, -1):
        inv[i - 1] = inv[i] * i % p  # 由 1/i! 倒推出 1/(i-1)!
    return tuple(fact), tuple(inv)


def lucas(n: int, k: int, p: int) -> int:
    """C(n, k) mod p（p 为质数）。

    逐位拆开 n、k 的 p 进制表示：C(n, k) ≡ ∏ C(n_i, k_i) (mod p)。
    某一位上 k_i > n_i 时整个乘积为 0，这正是 p | C(n, k) 的情形，
    所以不需要像扩展 Lucas 那样单独处理 p 的幂次。
    """
    if k < 0 or k > n:
        return 0
    fact, inv = pascal_row(p)
    result = 1
    while n or k:
        ni, ki = n % p, k % p
        if ki > ni:
            return 0
        result = result * fact[ni] % p * inv[ki] % p * inv[ni - ki] % p
        n, k = n // p, k // p
    return result


def reduced_exponent(n: int) -> int:
    """P mod (MOD-1)，其中 P = Σ_{k | n} C(n, k)。"""
    ks = divisors(n)  # 四个模数共用同一份约数表，只需枚举一次
    r, M = 0, 1  # 已合并部分的余数与模数，M 始终与下一个素因子互素
    for p in CRT_MODS:
        residue = sum(lucas(n, k, p) for k in ks) % p
        t = (residue - r) * pow(M, -1, p) % p  # 令 r + t * M ≡ residue (mod p)
        r, M = r + t * M, M * p
    return r


def ancient_pig(n: int, g: int) -> int:
    """研究古代文字的代价 G^P mod 999911659，P 是对全部约数 k 的 C(n, n/k) 之和。"""
    if g % MOD == 0:
        return 0  # G 是模数的倍数，任何正次幂都是 0
    # n/k 也遍历全部约数，所以对 k 求和与对 n/k 求和是同一件事
    return pow(g, reduced_exponent(n), MOD)


def solve() -> None:
    n, g = map(int, sys.stdin.buffer.read().split())
    print(ancient_pig(n, g))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 00:35
 * update_at: 2026-10-06 00:35
 */
// 古代猪文：求 G^P mod 999911659，其中 P = Σ_{k | N} C(N, k)。
// 链路：费马小定理降幂 -> P mod (MOD-1)，MOD-1 = 2×3×4679×35617，
// 四个素因子下分别用 Lucas 定理求 P，最后用中国剩余定理合并出指数。
#include <cstdio>

typedef long long ll;

const ll MOD = 999911659;      // 题目模数，是质数
const int PCNT = 4;
const ll crt_p[PCNT] = {2, 3, 4679, 35617}; // MOD1 的全部素因子
const ll MAXP = 35617;         // 最大的素因子，决定阶乘表大小

// 预处理每个素因子 p 下的阶乘表 fact[i] = i! mod p 和逆元表 inv[i] = (i!)^{-1} mod p
ll fact[PCNT][MAXP];
ll inv[PCNT][MAXP];

ll qpow(ll base, ll e, ll mod) { // 快速幂：base^e mod mod
    ll ans = 1;
    base %= mod;
    while (e > 0) {
        if (e & 1) ans = ans * base % mod;
        base = base * base % mod;
        e >>= 1;
    }
    return ans;
}

// 一次性建出四个素因子共用的两张表，逆元表由末项倒推
void build_tables() {
    for (int i = 0; i < PCNT; ++i) {
        ll p = crt_p[i];
        fact[i][0] = 1;
        for (ll j = 1; j < p; ++j) fact[i][j] = fact[i][j - 1] * j % p;
        inv[i][p - 1] = qpow(fact[i][p - 1], p - 2, p); // p 是质数，逆元 = 幂 p-2
        for (ll j = p - 1; j >= 1; --j) inv[i][j - 1] = inv[i][j] * j % p;
    }
}

// C(n, k) mod p，p 为质数，逐位拆 p 进制（Lucas 定理）
// 某一位上 k_i > n_i 时整个乘积为 0，这正好覆盖了 p | C(n, k) 的情形
ll lucas(int id, ll n, ll k) {
    ll p = crt_p[id];
    ll ans = 1;
    while (n > 0 || k > 0) {
        ll ni = n % p, ki = k % p;
        if (ki > ni) return 0;      // 这一位选多了，组合数被 p 整除
        ans = ans * fact[id][ni] % p * inv[id][ki] % p * inv[id][ni - ki] % p;
        n /= p;
        k /= p;
    }
    return ans;
}

// 求 P mod p（p 是 MOD1 的一个素因子），N 的约数现场枚举、不落地保存
ll sum_crt(ll n, int id) {
    ll p = crt_p[id];
    ll sum = 0;
    for (ll d = 1; d * d <= n; ++d) {
        if (n % d != 0) continue;
        sum = (sum + lucas(id, n, d)) % p; // k 与 N/k 都遍历全部约数，各收一次
        if (d != n / d)                    // 完全平方数时中间那个约数只算一次
            sum = (sum + lucas(id, n, n / d)) % p;
    }
    return sum;
}

int main() {
    ll n, g;
    scanf("%lld %lld", &n, &g);

    if (g % MOD == 0) { // G 是模数的倍数，任何正次幂都是 0，且费马降幂失效
        printf("0\n");
        return 0;
    }

    build_tables();

    // CRT 逐项增量合并：r 是已合并部分的余数，M 是已合并部分的模数，
    // M 始终是若干不同素因子之积，与下一个 p 互素，逆元必然存在
    ll r = 0, M = 1;
    for (int i = 0; i < PCNT; ++i) {
        ll p = crt_p[i];
        ll residue = sum_crt(n, i);
        ll t = (residue - r) % p * qpow(M % p, p - 2, p) % p; // 令 r + t*M ≡ residue (mod p)
        if (t < 0) t += p;
        r = r + t * M; // 不取模也不会溢出：最终 r < 999911658，中间 t*M < 35617*MOD1
        M = M * p;
    }

    // 费马小定理：G^P ≡ G^(P mod (MOD-1)) (mod MOD)
    printf("%lld\n", qpow(g % MOD, r, MOD));
    return 0;
}

复杂度

记 $d(N)$ 为 $N$ 的约数个数（ $N \leqslant 10^9$ 时 $d(N) \leqslant 1344$ ）。

时间复杂度： $O\!\left(\sqrt N + d(N)\log N + \log \text{MOD}\right)$ 。枚举约数 $O(\sqrt N)$ ； $d(N)$ 次组合数各由 Lucas 在 $O(\log N)$ 位内求出，四个模数是常数倍；快速幂 $O(\log \text{MOD})$ ；建表为固定开销。
空间复杂度： $O\!\left(\sum p + d(N)\right)$ ，即 $4679 + 35617$ 级别的两张阶乘表与逆元表，加上约数列表，实测峰值约 18 MB，满足 128 MB。

总结

题目难在"中间量太大"，全部推理都在做分而治之：先用费马小定理把指数从 $10^9$ 位压到 $999911658$ 以下，再把模数 $999911658$ 拆成四个素数之积（各用 Lucas 定理独立求解），最后用中国剩余定理把四个余数拼回同一个指数。整条链路上没有一步需要真正写出巨大的组合数， $N = 10^9$ 也只需约 $3.2 \times 10^4$ 次试除，加上 $4\,d(N)$ 次 $O(\log N)$ 的取模运算。

图示解析

下图是完整数据流：输入 $N, G$ 后，约数集合同时喂给四个 Lucas 分支，四条余数经 CRT 合并成一个指数，最后交给快速幂。

flowchart TD
    In["读入 N, G"] --> D["枚举 N 的全部约数 k"]
    In --> Z{"G mod 999911659 == 0 ?"}
    Z -- 是 --> Out0["输出 0"]
    Z -- 否 --> L2["p = 2: Lucas 求 C(N,k) mod 2"]
    D --> L2
    D --> L3["p = 3: Lucas 求 C(N,k) mod 3"]
    D --> L4679["p = 4679: Lucas 求 C(N,k) mod 4679"]
    D --> L35617["p = 35617: Lucas 求 C(N,k) mod 35617"]
    L2 --> S["各分支对 k 求和, 得 P mod p"]
    L3 --> S
    L4679 --> S
    L35617 --> S
    S --> C["CRT 合并四个余数, 得 r = P mod 999911658"]
    C --> F["快速幂 G^r mod 999911659"]
    F --> Out["输出答案"]

观察重点有三处：约数 $k$ 只枚举一次却同时被四个分支复用；每个分支内部 $\binom Nk$ 由 Lucas 逐位分解，位数不超过 $\log_2 N \approx 30$ ； CRT 是唯一的汇合点，它之后只剩一次快速幂。