第 6 章 · 01 数论（对应 docs/math/number-theory/）

第 6 章 · 01 数论（对应 docs/math/number-theory/）

本节定位：对应 OI Wiki docs/math/number-theory/（共 33 篇，OI Wiki 最深的子目录）。难度：进阶到高阶。前置依赖：算法基础（第 2 章）、基本取模运算。本节是非难点导读节，把 33 篇按"工具 → 经典定理 → 省选级反演"分四层串起来，莫比乌斯反演和杜教筛是省选级难点但本节只做导读，深入请回 Wiki。

⚠️ 注意：数论是 OI Wiki 内容最密集的部分，公式极多。本节只导航并点出"哪些必会、哪些是省选级"，不重写 Wiki 的证明。读 Wiki 时建议按本节给出的顺序，不要跳。

知识地图

第一层：素数与筛法（必会，地基）

• 素数判定（docs/math/number-theory/prime.md）：试除法 O(√n)，枚举到 √n 即可；大数（如 10¹⁸）用 Miller-Rabin 概率判定（docs/math/number-theory/prime.md 同页后半），基于费马小思想，用若干个底数测试，准确率极高。
• 埃氏筛（docs/math/number-theory/sieve.md）：O(n log log n)，每个合数被它的质因子多次标记，实现简单但不够快。
• 欧拉线性筛（docs/math/number-theory/sieve.md）：O(n)，核心是"每个合数只被它的最小质因子筛一次"。线性筛是数论题的标配预处理，欧拉函数、莫比乌斯函数都能在筛的过程中顺手求出。
• 质因数分解（docs/math/number-theory/prime.md）：试除 O(√n)；大数用 Pollard-Rho（docs/math/number-theory/pollard-rho.md），期望 O(n^(1/4))。

💡 学习提示：线性筛是后续欧拉函数、莫比乌斯函数预处理的基础，必须能默写。关键是内层循环遇到 i % prime[j] == 0 就 break，保证每个合数只被最小质因子筛掉。这段代码几乎每场数论题都要写。

第二层：欧拉函数与费马小定理（必会）

• 欧拉函数 φ(n)（docs/math/number-theory/euler.md）：≤ n 且与 n 互质的个数。如 φ(6)=2（1、5）。φ 是积性函数（互质时 φ(ab)=φ(a)φ(b)），可在线性筛里顺手预处理。欧拉定理推广了费马：a^φ(m) ≡ 1 (mod m)（a、m 互质），是求逆元的更一般基础。
• 费马小定理（docs/math/number-theory/fermat.md）：p 为质数且 gcd(a,p)=1 时 a^(p-1) ≡ 1 (mod p)。这是求逆元（模质数）的工具，也是快速幂取模、Miller-Rabin 素性测试的理论基础。竞赛里 a^(p-2) mod p 求逆元就是直接用它。

第三层：逆元与方程（必会）

• 乘法逆元（docs/math/number-theory/inverse.md）：两条路——
  • 模数 p 为质数：a^(-1) ≡ a^(p-2) (mod p)（费马小定理 + 快速幂），O(log p)。
  • 模数任意：扩展欧几里得 exgcd（docs/math/number-theory/euclidean.md）解 ax + by = gcd(a,b)，得到 x 即逆元（要求 gcd(a,模数)=1）。
  • 批量求逆元：用递推 inv[i] = -(p/i) * inv[p%i] mod p，O(n) 求出 1..n 所有逆元。
• 中国剩余定理 CRT（docs/math/number-theory/crt.md）：解模数两两互质的同余方程组，"孙子定理"。扩展 CRT（docs/math/number-theory/crt.md 后半）可处理模数不互质的情况（合并两个方程）。
• 同余方程（docs/math/number-theory/congruence-equation.md）：一次同余方程用 exgcd；高次用 BSGS 等（进阶）。

⚠️ 注意：竞赛里取模除法必须用逆元，不能直接除。求逆元优先用费马小定理（p 是质数时），不满足才用 exgcd。这两个模板都要能默写。批量逆元的递推公式也要记，n 大时单点费马会 TLE。

第四层：莫比乌斯反演（省选级，难点）

• 莫比乌斯函数 μ（docs/math/number-theory/mobius.md）：μ(n) 按质因子个数取值——n 有平方因子时 μ=0；否则质因子数为偶 μ=1，为奇 μ=-1。可在线性筛预处理。
• 莫比乌斯反演公式：若 f(n) = Σ_{d|n} g(d)，则 g(n) = Σ_{d|n} μ(d) f(n/d)。这是把"求和换序"的核心工具。竞赛里典型套路是：把含 gcd 的求和用莫比乌斯反演化简成整除求和。
• 整除分块（docs/math/number-theory/sqrt-decomposition.md）：求 Σ floor(n/i) 这类和时（i 从 1 到 n），把 i 按"商相同"分成 O(√n) 块，每块整段求和，O(√n) 加速。是反演题计算答案的标准技巧。
• 狄利克雷卷积（docs/math/number-theory/dirichlet.md）：(f*g)(n) = Σ_{d|n} f(d) g(n/d)，是莫比乌斯反演的代数基础。

💡 学习提示：莫比乌斯反演是省选的"分水岭"。初学别贪多，先把"推式子 + 整除分块"练熟（典型题如求 Σ gcd(i,j)），再学复杂反演。推式子时记住几个常用结论（如 Σ_{d|n} μ(d) = [n==1]）。

第五层：杜教筛（省选级，难点）

• 杜教筛（docs/math/number-theory/du.md）：求数论函数前缀和 S(n) = Σf(i)，复杂度 O(n^(2/3))。当 n 大到 10¹⁰（线性筛跑不动）时使用。
• 思路：找一个配对函数 g，利用狄利克雷卷积 (f*g) 的前缀和反推出 S(n)，递归求解 + 预处理小范围（到 n^(2/3)）+ 记忆化（用哈希表存已算过的 S）。
• 典型应用：n ≤ 10¹⁰ 时求欧拉函数前缀和、莫比乌斯函数前缀和。
• 类似的还有 Min_25 筛（docs/math/number-theory/min-25.md）、Powerful Number 筛，属于更进阶的求和工具。

学习建议

1. 必会清单（任何比赛都用得上）：欧拉线性筛、欧拉函数、乘法逆元（费马 + exgcd）、快速幂。这四个是数论题的"螺丝刀"，必须当天能默写。
2. 省选级清单：莫比乌斯反演 + 整除分块、杜教筛。这些是 CSP/NOIP 不会考、但省选必考的内容，建议在高阶阶段集中突破。
3. 读 Wiki 顺序：prime.md → sieve.md → euler.md → fermat.md → inverse.md → euclidean.md → crt.md → mobius.md → sqrt-decomposition.md → du.md。前 7 个是地基，后 3 个是高阶。
4. 公式要手推：数论的 Wiki 页面公式密集，别只看结论。每条公式至少在纸上代一个具体数验证。
5. 配合刷题：筛法和逆元有大量模板题（如洛谷 P3383 线性筛、P3811 乘法逆元、P1082 扩展欧几里得），先过模板再学理论。莫比乌斯反演可从 P3455 求 gcd 之和入门，杜教筛从 P4213 模板题入门。
6. 按阶段分配精力：CSP/NOIP 阶段只学前三层（筛法/逆元/CRT）；省选阶段再攻莫比乌斯反演和杜教筛。不要提前硬啃反演，那是省选冲刺的内容。

💡 学习提示：数论是"公式多但模型少"的学科。把"线性筛 + 逆元 + 反演"这三类吃透，80% 的数论题都能套。不要追求把 33 篇全背下来，要建立"遇到什么题用什么工具"的索引。

本节要点

• 第一层地基：欧拉线性筛 O(n)、素数判定（试除/Miller-Rabin）。
• 第二层定理：欧拉函数 φ、费马小定理 a^(p-1) ≡ 1。
• 第三层逆元：费马小定理求逆（p 质数）+ 扩展欧几里得（任意模数）+ CRT。
• 第四层反演：莫比乌斯函数 μ、反演公式、整除分块 O(√n)。
• 第五层杜教筛：前缀和 O(n^(2/3))，省选级。
• 必会的是筛法和逆元，反演和杜教筛留到省选冲刺；深入见 docs/math/number-theory/ 各页。