📐 第八部分：数学
竞赛编程的另一半战场。数论、筛法、组合计数、矩阵加速、博弈论——USACO Silver 到 Platinum 的数学工具箱。
📚 5 章 · ⏱️ 预计 3-5 周 · 🎯 目标：USACO Silver → Platinum
第八部分：数学
预计用时：4-6 周
数学是竞赛编程的另一半。USACO 每场比赛几乎都有一道数学题，从 Bronze 的整除判断到 Platinum 的矩阵加速递推。本部分把散落各处（原附录）的数学内容整合为一条从易到难的学习路径。
涵盖的主题
| 章节 | 主题 | 核心思想 |
|---|---|---|
| 第 8.1 章 🥈 | 数论基础 | 模运算、快速幂、模逆元、GCD 与扩展欧几里得 |
| 第 8.2 章 🥇 | 素数筛法与积性函数 | 埃筛、欧拉线性筛、欧拉 φ、中国剩余定理 |
| 第 8.3 章 🥇 | 组合数学 | C(n,k) mod p、组合恒等式、隔板法、容斥原理 |
| 第 8.4 章 💎 | 矩阵快速幂 | 矩阵乘法、线性递推的 O(k³ log n) 加速 |
| 第 8.5 章 🥇 | 博弈论入门 | Nim 和、SG 函数与 SG 定理 |
学习路线
- 第 8.1 章是地基——模运算和快速幂几乎出现在每道计数题里，必须先掌握。
- 第 8.2、8.3 章是 Gold 数学题主战场——筛法与组合计数是 USACO Gold 数学题的两大高频考点。
- 第 8.4 章面向 Platinum——矩阵快速幂在 Gold 出现频率不高，但它是 Platinum 分治/数据结构题的常客。
- 第 8.5 章是独立专题——博弈论相对独立，可按需选读。
复杂度速查
| 操作 | 方法 | 时间复杂度 |
|---|---|---|
| a^b mod p | 快速幂 | O(log b) |
| a⁻¹ mod p（p 素数） | 费马小定理 + 快速幂 | O(log p) |
| gcd(a, b) | 欧几里得 / 辗转相除 | O(log min(a,b)) |
| ax + by = c 的解 | 扩展欧几里得 | O(log min(a,b)) |
| 1~n 的所有素数 | 埃拉托斯特尼筛 | O(n log log n) |
| 1~n 的所有素数 | 欧拉线性筛 | O(n) |
| 1~n 的欧拉 φ 值 | 线性筛同时求 φ | O(n) |
| C(n,k)（单次） | 逆元法 | O(k log p) |
| C(n,k)（多次询问） | 阶乘 + 逆元预处理 | O(N) 预处理 O(1) 查询 |
| n 项线性递推第 n 项 | 矩阵快速幂 | O(k³ log n) |
本部分学习建议
- 先修知识：第 2.6 章（位运算）和第 3.2 章（前缀和）会让第 8.1-8.3 章的学习更顺畅，但不是硬性前置。
- 模运算代码一定要自己写一遍——
(a * b) % p的溢出陷阱（用long long还是被乘法中间结果坑）只有亲手调试过才记得住。 - 组合数学配合第 6.7 章（概率期望与计数 DP）食用更佳——本章提供公式工具，DP 章提供状态设计思路。