# GESP 十级编程能力认证讲义：数论与算法进阶

## 第一模块：乘法逆元 (Modular Multiplicative Inverse)

### 1. 知识点拆解
*   **定义**：若 $ax \equiv 1 \pmod m$，则称 $x$ 为 $a$ 模 $m$ 的逆元，记作 $a^{-1}$。
*   **求解方法**：
    1.  **费马小定理**：若 $m$ 为质数，则 $a^{m-2} \equiv a^{-1} \pmod m$。
    2.  **扩展欧几里得 (Exgcd)**：求解 $ax + my = 1$，得到的 $x$ 即为逆元。适用于 $gcd(a, m) = 1$ 但 $m$ 不是质数的情况。
    3.  **线性递推**：$O(n)$ 时间内求出 $1 \dots n$ 的所有逆元。
*   **应用**：在模运算中处理除法。$(a / b) \pmod m \Rightarrow (a \times b^{-1}) \pmod m$。

### 2. 具体例子
**例子 1.1**：求 3 模 7 的逆元。
根据费马小定理：$3^{7-2} = 3^5 = 243$。
$243 \div 7 = 34 \dots 5$。
所以 $3^{-1} \equiv 5 \pmod 7$。验证：$3 \times 5 = 15 \equiv 1 \pmod 7$。

### 3. 练习巩固
1.  **【简单】单选题**：若 $p$ 是质数，求解 $a \pmod p$ 的逆元最简便的方法是（ ）。
    A. 暴力枚举  B. 费马小定理  C. 卢卡斯定理  D. 中国剩余定理
2.  **【中等】填空题**：使用扩展欧几里得算法求解 $5x + 7y = 1$，得到的一组整数解中，$x$ 的值可以为 ______，此时 $x$ 是 5 模 7 的逆元。
3.  **【困难】阅读程序写结果**：
    ```cpp
    inv[1] = 1;
    for (int i = 2; i <= 5; ++i)
        inv[i] = (p - p / i) * inv[p % i] % p; 
    // 若 p = 7，计算 inv[3] 的值。
    ```
    输出：__________

---

## 第二模块：卢卡斯定理 (Lucas Theorem)

### 1. 知识点拆解
*   **用途**：求解大组合数取模。适用于 $n, m$ 很大（如 $10^{18}$），但模数 $p$ 较小（如 $10^5$ 且为质数）的情况。
*   **公式**：$\binom{n}{m} \equiv \binom{n/p}{m/p} \cdot \binom{n \pmod p}{m \pmod p} \pmod p$。
*   **核心逻辑**：将大组合数拆解为 $p$ 进制下的每一位组合数相乘，利用递归实现。

### 2. 具体例子
**例子 2.1**：计算 $\binom{10}{3} \pmod 7$。
1. $\binom{10}{3} \equiv \binom{10/7}{3/7} \cdot \binom{10\%7}{3\%7} \pmod 7$
2. $\Rightarrow \binom{1}{0} \cdot \binom{3}{3} \pmod 7$
3. $\Rightarrow 1 \times 1 = 1 \pmod 7$。
（验证：$\binom{10}{3} = 120$，$120 \div 7 = 17 \dots 1$。结果正确。）

### 3. 练习巩固
1.  **【简单】对错题**：卢卡斯定理可以处理模数 $p$ 为合数的情况。（ ）
2.  **【中等】单选题**：要计算 $\binom{10^{12}}{10^9} \pmod{10^5+3}$，应优先选用的算法是（ ）。
    A. 动态规划  B. 逆元+阶乘  C. 卢卡斯定理  D. 快速幂
3.  **【困难】阅读程序填空**：
    ```cpp
    long long Lucas(long long n, long long m, int p) {
        if (m == 0) return 1;
        return (Lucas(n / p, m / p, p) * __________) % p;
    }
    // 提示：此处应调用求解普通组合数 C(n % p, m % p) 的函数
    ```

---

## 第三模块：中国剩余定理 (Chinese Remainder Theorem, CRT)

### 1. 知识点拆解
*   **用途**：求解一元线性同余方程组（如“韩信点兵”问题）。
    $x \equiv a_1 \pmod{m_1}$
    $x \equiv a_2 \pmod{m_2}$
*   **条件**：$m_1, m_2 \dots m_k$ 两两互质。
*   **公式步骤**：
    1. 计算 $M = m_1 \times m_2 \times \dots$
    2. 计算 $M_i = M / m_i$
    3. 计算 $t_i$ 为 $M_i$ 模 $m_i$ 的逆元
    4. 结果 $x = \sum (a_i \cdot M_i \cdot t_i) \pmod M$

### 2. 具体例子
**例子 3.1**：$x \equiv 2 \pmod 3, x \equiv 3 \pmod 5$。
1. $M = 15$。
2. $M_1 = 5, M_2 = 3$。
3. $5 \times t_1 \equiv 1 \pmod 3 \Rightarrow t_1 = 2$。
4. $3 \times t_2 \equiv 1 \pmod 5 \Rightarrow t_2 = 2$。
5. $x = (2 \times 5 \times 2 + 3 \times 3 \times 2) = 20 + 18 = 38 \equiv 8 \pmod{15}$。

### 3. 练习巩固
1.  **【简单】单选题**：中国剩余定理解决的是（ ）问题。
    A. 离散对数  B. 线性同余方程组  C. 质因数分解  D. 最大公约数
2.  **【中等】填空题**：一个数除以 3 余 2，除以 7 余 1，则满足条件的最小正整数是 ______。
3.  **【困难】对错题**：如果模数 $m_i$ 之间不互质，则无法使用传统的 CRT 求解，需要使用扩展中国剩余定理 (EXCRT)。（ ）

---

## 第四模块：算法进阶——AC 自动机与网络流

### 1. 知识点拆解
*   **AC 自动机**：
    *   **本质**：在 Trie 树上跑 KMP。
    *   **Fail 指针**：指向当前状态的最长后缀所代表的状态。用于多模式串匹配。
*   **网络流 (Network Flow)**：
    *   **最大流**：Dinic 算法（分层图 + 当前弧优化）。
    *   **最小割**：最大流等于最小割。常用于解决二者选其一的代价问题。

### 2. 具体例子
**例子 4.1**：AC 自动机中的 `fail`。
若模式串有 `he` 和 `she`。当在 `she` 的 `e` 匹配完后，其 `fail` 指针应指向 `he` 的 `e`，因为 `he` 是 `she` 的后缀。

### 3. 练习巩固
1.  **【简单】单选题**：AC 自动机构建 `fail` 指针时采用的遍历方式是（ ）。
    A. 前序遍历  B. 后序遍历  C. 层序遍历 (BFS)  D. 深度优先 (DFS)
2.  **【中等】对错题**：在 Dinic 算法中，如果当前节点到汇点没有增广路，则可以通过“炸层”操作将其层级设为 -1，以减少无效搜索。（ ）
3.  **【困难】填空题**：一个流网络中，源点到汇点的最大流量为 100，则该网络的最小割容量为 ______。

---

## 教练参考答案与解析

### 第一模块
1. **B**。
2. **3**。（$5 \times 3 = 15 = 2 \times 7 + 1$）。
3. **5**。推导：`inv[3] = (7 - 7/3) * inv[7%3] % 7 = (7-2) * inv[1] % 7 = 5 * 1 = 5`。

### 第二模块
1. **错**。必须要求 $p$ 是质数。
2. **C**。
3. **C(n % p, m % p, p)**。

### 第三模块
1. **B**。
2. **8**。（$8 \% 3 = 2, 8 \% 7 = 1$）。
3. **对**。不互质会导致逆元不存在，需要合并方程。

### 第四模块
1. **C**。
2. **对**。这就是当前弧优化和残量网络剪枝的思想。
3. **100**。

---
**教练寄语**：
十级的内容已经触及了计算机科学中极其精妙的数学对称美。**逆元**让除法重获新生，**卢卡斯**让巨大的数字变得渺小，而**网络流**则是一种顶级的建模艺术。
在这个阶段，**多写证明，少背模板**。当你理解了为什么 $C(n, m) = C(n/p, m/p) \dots$ 的那一刻，你才真正掌握了它。加油，未来的科学家！

GESP 十级编程能力认证讲义：数论与算法进阶

第一模块：乘法逆元 (Modular Multiplicative Inverse)

1. 知识点拆解

定义：若 $ax \equiv 1 \pmod m$，则称 $x$ 为 $a$ 模 $m$ 的逆元，记作 $a^{-1}$。
求解方法：
1. 费马小定理：若 $m$ 为质数，则 $a^{m-2} \equiv a^{-1} \pmod m$。
2. 扩展欧几里得 (Exgcd)：求解 $ax + my = 1$，得到的 $x$ 即为逆元。适用于 $gcd(a, m) = 1$ 但 $m$ 不是质数的情况。
3. 线性递推：$O(n)$ 时间内求出 $1 \dots n$ 的所有逆元。
应用：在模运算中处理除法。$(a / b) \pmod m \Rightarrow (a \times b^{-1}) \pmod m$。

2. 具体例子

例子 1.1：求 3 模 7 的逆元。根据费马小定理：$3^{7-2} = 3^5 = 243$。 $243 \div 7 = 34 \dots 5$。所以 $3^{-1} \equiv 5 \pmod 7$。验证：$3 \times 5 = 15 \equiv 1 \pmod 7$。

3. 练习巩固

【简单】单选题：若 $p$ 是质数，求解 $a \pmod p$ 的逆元最简便的方法是（）。 A. 暴力枚举 B. 费马小定理 C. 卢卡斯定理 D. 中国剩余定理
【中等】填空题：使用扩展欧几里得算法求解 $5x + 7y = 1$，得到的一组整数解中，$x$ 的值可以为 ______，此时 $x$ 是 5 模 7 的逆元。
【困难】阅读程序写结果： cpp inv[1] = 1; for (int i = 2; i <= 5; ++i) inv[i] = (p - p / i) * inv[p % i] % p; // 若 p = 7，计算 inv[3] 的值。 输出：____

第二模块：卢卡斯定理 (Lucas Theorem)

1. 知识点拆解

用途：求解大组合数取模。适用于 $n, m$ 很大（如 $10^{18}$），但模数 $p$ 较小（如 $10^5$ 且为质数）的情况。
公式：$\binom{n}{m} \equiv \binom{n/p}{m/p} \cdot \binom{n \pmod p}{m \pmod p} \pmod p$。
核心逻辑：将大组合数拆解为 $p$ 进制下的每一位组合数相乘，利用递归实现。

2. 具体例子

例子 2.1：计算 $\binom{10}{3} \pmod 7$。 1. $\binom{10}{3} \equiv \binom{10/7}{3/7} \cdot \binom{10\%7}{3\%7} \pmod 7$ 2. $\Rightarrow \binom{1}{0} \cdot \binom{3}{3} \pmod 7$ 3. $\Rightarrow 1 \times 1 = 1 \pmod 7$。（验证：$\binom{10}{3} = 120$，$120 \div 7 = 17 \dots 1$。结果正确。）

3. 练习巩固

【简单】对错题：卢卡斯定理可以处理模数 $p$ 为合数的情况。（）
【中等】单选题：要计算 $\binom{10^{12}}{10^9} \pmod{10^5+3}$，应优先选用的算法是（）。 A. 动态规划 B. 逆元+阶乘 C. 卢卡斯定理 D. 快速幂
【困难】阅读程序填空： cpp long long Lucas(long long n, long long m, int p) { if (m == 0) return 1; return (Lucas(n / p, m / p, p) * __________) % p; } // 提示：此处应调用求解普通组合数 C(n % p, m % p) 的函数

第三模块：中国剩余定理 (Chinese Remainder Theorem, CRT)

1. 知识点拆解

用途：求解一元线性同余方程组（如“韩信点兵”问题）。 $x \equiv a_1 \pmod{m_1}$ $x \equiv a_2 \pmod{m_2}$
条件：$m_1, m_2 \dots m_k$ 两两互质。
公式步骤：
1. 计算 $M = m_1 \times m_2 \times \dots$
2. 计算 $M_i = M / m_i$
3. 计算 $t_i$ 为 $M_i$ 模 $m_i$ 的逆元
4. 结果 $x = \sum (a_i \cdot M_i \cdot t_i) \pmod M$

2. 具体例子

例子 3.1：$x \equiv 2 \pmod 3, x \equiv 3 \pmod 5$。 1. $M = 15$。 2. $M_1 = 5, M_2 = 3$。 3. $5 \times t_1 \equiv 1 \pmod 3 \Rightarrow t_1 = 2$。 4. $3 \times t_2 \equiv 1 \pmod 5 \Rightarrow t_2 = 2$。 5. $x = (2 \times 5 \times 2 + 3 \times 3 \times 2) = 20 + 18 = 38 \equiv 8 \pmod{15}$。

3. 练习巩固

【简单】单选题：中国剩余定理解决的是（）问题。 A. 离散对数 B. 线性同余方程组 C. 质因数分解 D. 最大公约数
【中等】填空题：一个数除以 3 余 2，除以 7 余 1，则满足条件的最小正整数是 ______。
【困难】对错题：如果模数 $m_i$ 之间不互质，则无法使用传统的 CRT 求解，需要使用扩展中国剩余定理 (EXCRT)。（）

第四模块：算法进阶——AC 自动机与网络流

1. 知识点拆解

AC 自动机：
- 本质：在 Trie 树上跑 KMP。
- Fail 指针：指向当前状态的最长后缀所代表的状态。用于多模式串匹配。
网络流 (Network Flow)：
- 最大流：Dinic 算法（分层图 + 当前弧优化）。
- 最小割：最大流等于最小割。常用于解决二者选其一的代价问题。

2. 具体例子

例子 4.1：AC 自动机中的 fail。若模式串有 he 和 she。当在 she 的 e 匹配完后，其 fail 指针应指向 he 的 e，因为 he 是 she 的后缀。

3. 练习巩固

【简单】单选题：AC 自动机构建 fail 指针时采用的遍历方式是（）。 A. 前序遍历 B. 后序遍历 C. 层序遍历 (BFS) D. 深度优先 (DFS)
【中等】对错题：在 Dinic 算法中，如果当前节点到汇点没有增广路，则可以通过“炸层”操作将其层级设为 -1，以减少无效搜索。（）
【困难】填空题：一个流网络中，源点到汇点的最大流量为 100，则该网络的最小割容量为 ______。

教练参考答案与解析

第一模块

B。
3。（$5 \times 3 = 15 = 2 \times 7 + 1$）。
5。推导：inv[3] = (7 - 7/3) * inv[7%3] % 7 = (7-2) * inv[1] % 7 = 5 * 1 = 5。

第二模块

错。必须要求 $p$ 是质数。
C。
C(n % p, m % p, p)。

第三模块

B。
8。（$8 \% 3 = 2, 8 \% 7 = 1$）。
对。不互质会导致逆元不存在，需要合并方程。

第四模块

C。
对。这就是当前弧优化和残量网络剪枝的思想。
100。

教练寄语：十级的内容已经触及了计算机科学中极其精妙的数学对称美。逆元让除法重获新生，卢卡斯让巨大的数字变得渺小，而网络流则是一种顶级的建模艺术。在这个阶段，多写证明，少背模板。当你理解了为什么 $C(n, m) = C(n/p, m/p) \dots$ 的那一刻，你才真正掌握了它。加油，未来的科学家！

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com