如果你在算法竞赛里被数论题虐过大概率见过这两样东西一本被大家叫做“紫薯”的紫色封面算法书一个圈内默认必刷的数论基础专题。把“紫薯第10章数学”和“专题14数论基础”放在一起学是我见过最扎实的数论入门路径。这篇文章不打算复述书里的公式而是把我在啃完这套组合后的整个思考过程、代码细节和踩坑记录梳理出来给正准备硬啃这块骨头的朋友做一个参考。1. 这套组合到底解决什么问题1.1 数论是竞赛里最容易被放弃的板块很多学算法的人对图论、动态规划都能聊几句一提到数论就摇头。原因很现实数论题很少给你一个可以直接套的模板它考察的是你对数字本质的理解。你可以在完全不懂原理的情况下背熟一个最短路板子但数论题做不到因为同一道题稍微改一下数据范围算法就得换一个层次。但数论在竞赛里的占比一点都不低。无论是网络赛、区域赛还是校内选拔质数、同余、欧拉函数、组合数取模都是高频考点。哪怕不考纯数论题很多动态规划、概率期望、数据结构题在后半段也会突然冒出一个“对 1e97 取模”这里的模运算、逆元、组合数都是数论基础。换句话说数论不是一门可以跳过的选修课它是支撑很多其他算法的基础设施。我自己最早的时候也走过弯路先去背了一堆公式见到题就翻笔记结果换个条件就不会了。后来发现问题的根源不是笨而是知识没有形成结构。书上的定理和题集里的题目是两套语言中间缺了一座桥。后来我把“紫薯第10章数学”和专题14数论基础结合起来学才终于把零散的知识点串成了一条线。1.2 紫薯讲原理专题练代码两套资料的分工非常清晰。“紫薯”第10章数学负责讲原理它从质数、约数、同余开始一步一步把定理推给你看连为什么要有欧拉函数、为什么中国剩余定理长成那样都交代得明明白白。专题14数论基础则负责给题目它按知识点把常见题型排好让你把刚学的定理放到真实题目里验证。我的配合方法很笨但很有效每看一章紫薯先把书里的模板代码抄一遍手推一个小例子确认自己理解然后去专题14里找对应知识点的题目做。看书看到的是“原来如此”做题感受到的是“卧槽这里居然要这样转化”两者缺一不可。只看书不去做题你会觉得自己全会了一合上书大脑空白只刷题不看书你会一直停留在“这题我见过但是换个问法就没思路”的阶段。如果你是第一次接触这套组合建议按下面的节奏来先花一周把紫薯第10章的质数、约数、同余三节读完再把专题14里对应的基础题刷掉不用贪多每天一到两题就够。数论最重要的不是题量而是每个结论你都能用自己的话解释清楚。2. 核心知识点拆解与代码细节2.1 线性筛法一份代码解决筛素数和其他一堆事先说最基础的质数筛。埃氏筛很好理解复杂度是 O(n log log n)在 n 到 1e7 的范围内完全够用。但专题14里很多题会顺带要你求欧拉函数、莫比乌斯函数这时候线性筛才是正解。它的核心思想是每个合数只被它的最小质因数筛掉一次。const int N 1000005; int primes[N], cnt; bool st[N]; void get_primes(int n) { for (int i 2; i n; i) { if (!st[i]) primes[cnt] i; for (int j 0; primes[j] n / i; j) { st[primes[j] * i] true; if (i % primes[j] 0) break; } } }注意循环里的判断条件primes[j] n / i写成乘法primes[j] * i n容易溢出虽然 int 乘 int 在大部分题目里不至于出事但这个习惯建议一开始就养好。更关键的是if (i % primes[j] 0) break;这行它保证了每个合数只会被最小质因数访问到所以总复杂度是 O(n)。我见过不少初学者问埃氏筛那么短为什么要背线性筛因为在很多数论题里筛的过程不只是为了得到质数列表还要顺便维护其他信息。比如筛欧拉函数时if (i % primes[j] 0)的判断就是区分两种状态的关键分支。一旦你理解了这行的意义后面搞懂线性筛求欧拉函数、莫比乌斯函数就是水到渠成的事。另外提醒一句区间筛是专题14里的常客。当你要筛 [L, R] 范围内的质数而 L 和 R 非常大但 R-L 很小就不能直接开 1e9 的数组。这时只需要用 [2, sqrt(R)] 的质数去标记 [L, R] 的合数。这个是埃氏筛的扩展跟线性筛的代码不太一样建议亲手实现一次再做题。2.2 欧拉函数从定义到线性筛预处理欧拉函数 φ(n) 表示 1 到 n 中与 n 互质的整数个数。它有一个通式n 质因数分解为 p1^a1 * p2^a2 * ... 后φ(n) n * Π(1 - 1/pi)等价于 n * Π((pi - 1) / pi)。单点求欧拉函数用试除法就够了int phi(int n) { int res n; for (int i 2; i n / i; i) { if (n % i 0) { res res / i * (i - 1); while (n % i 0) n / i; } } if (n 1) res res / n * (n - 1); return res; }注意res res / i * (i - 1)这个顺序。如果先乘再除当 n 接近 1e9 且 i 很小时res 可能就在中间过程溢出了先除再乘几乎不影响精度还能防溢出。这个写法上的小心思是很多老选手踩过坑之后总结出来的。专题14里经常出现的是批量求欧拉函数比如求 1 到 n 所有数的欧拉函数之和。这个用线性筛可以做到 O(n)const int N 1000010; int phi[N], primes[N], cnt; bool st[N]; void get_phi(int n) { phi[1] 1; for (int i 2; i n; i) { if (!st[i]) { primes[cnt] i; phi[i] i - 1; } for (int j 0; primes[j] n / i; j) { st[primes[j] * i] true; if (i % primes[j] 0) { phi[primes[j] * i] phi[i] * primes[j]; break; } else { phi[primes[j] * i] phi[i] * (primes[j] - 1); } } } }解释一下两个分支当 i 已经被 primes[j] 整除说明 primes[j] 是 i 的最小质因数那么 primes[j]*i 相比 i 只是多乘了一个质因子欧拉函数总体乘上 primes[j]当 i 不被 primes[j] 整除说明 primes[j] 是新增的质因子欧拉函数要乘上 (primes[j] - 1)。这两个分支就是线性筛求欧拉函数的灵魂。欧拉函数最重要的副产品是欧拉定理若 gcd(a, n) 1则 a^φ(n) ≡ 1 (mod n)。当 n 是质数 p 时φ(p) p - 1就得到费马小定理 a^(p-1) ≡ 1 (mod p)。这条定理是后面求逆元的理论根基专题14里大量题都离不开它。2.3 扩展欧几里得一次递归把不定方程和逆元全搞定扩展欧几里得几乎是数论基础专题里最常考的核心。它能用来解 ax by gcd(a, b) 的整数解也可以用来求逆元、解同余方程。代码短但很多人是背下来的不知道递归到底发生了什么int exgcd(int a, int b, int x, int y) { if (!b) { x 1; y 0; return a; } int d exgcd(b, a % b, y, x); y - a / b * x; return d; }递归退出条件是 b 0此时 gcd a显然有一组解 x 1, y 0。回溯时递归返回的是满足 bx (a % b)y gcd(b, a % b) 的一组解我们通过交换参数让新 x 等于原来的 y再更新y - a / b * x就得到了满足 ax by gcd(a, b) 的解。我不知道你第一次看到这段代码是什么感觉反正我当时盯着看了半小时才转过弯。我的建议是拿 a6, b4 手推一遍递归过程把每层 x、y 的值写在纸上写完之后你会彻底理解为什么参数在递归里是被交换的。有了 exgcd 之后求逆元就很直接了。要求 a 在模 m 意义下的逆元相当于解 ax my 1前提是 gcd(a, m) 1。调用exgcd(a, m, x, y)后x 就是逆元最后对 m 取正int inv(int a, int m) { int x, y; int d exgcd(a, m, x, y); if (d ! 1) return -1; // 逆元不存在 return (x % m m) % m; }解一般同余方程 ax ≡ b (mod m) 也是这个套路先求 g gcd(a, m)如果 b 不能被 g 整除就无解否则两边同时除以 g用 exgcd 求新方程的一组解再乘倍数取模。专题14里很多题表面问的是“求最小正整数解”实际考的就是这个流程。2.4 中国剩余定理同余方程组的联立解法中国剩余定理解决的是模数两两互质的一组同余方程x ≡ a1 (mod m1) x ≡ a2 (mod m2) ... x ≡ ak (mod mk)设 M m1 * m2 * ... * mkMi M / mi则 x ≡ Σ ai * Mi * inv(Mi, mi) (mod M)。其中 inv(Mi, mi) 是 Mi 在模 mi 下的逆元要用 exgcd 求。实现如下int crt(vectorint a, vectorint m) { int M 1; for (int x : m) M * x; int res 0; for (int i 0; i a.size(); i) { int Mi M / m[i]; res a[i] * Mi % M * inv(Mi, m[i]) % M; res % M; } return (res M) % M; }这里面最容易出错的是每个乘法都要取模。a[i]、Mi、逆元这三个数在乘起来之前可能都小于 1e9但乘完就爆 int所以每步都要模。如果题目里的模数是两两不互质的基础 CRT 不成立需要改成扩展中国剩余定理思路是把方程两两合并x ≡ a1 (mod m1) 和 x ≡ a2 (mod m2) 联立成 x ≡ a1 m1 * t (mod lcm(m1, m2))这个合并过程又需要 exgcd。建议先把基础版练熟再去碰不互质的情况。我在专题14里遇到过几道不互质版 CRT第一次做的时候完全没头绪后来发现就是用 exgcd 合并方程跟基础版没有本质区别只是代码里多一个 gcd 判断分支。2.5 快速幂从矩阵到取模处处要用在开始做题之前建议把快速幂的板子也准备好。它和逆元、组合数取模、费马小定理强绑定几乎每场竞赛都会用到。int qpow(int a, int b, int mod) { int res 1 % mod; while (b) { if (b 1) res 1LL * res * a % mod; a 1LL * a * a % mod; b 1; } return res; }这里有个不起眼的细节res 1 % mod而不是直接res 1因为当 mod 1 时幂运算结果应该为 0否则会返回 1 导致边界 WA。这个坑我真实踩过是在做一道模数为 1 的变态数据时挂掉的。还有乘法溢出问题。用1LL * res * a在模数小于 1e9 时没问题但模数一旦接近 1e18两个 long long 相乘就会溢出。这种时候需要把快速幂里的乘法替换成“快速乘”本质上是一个二进制拆分的加法代码逻辑和快速幂几乎一样。专题14里有些题模数很大建议提前写好这个函数备用。3. 专题14刷题实操顺序、套路和复盘方法3.1 按“知识块”刷而不是按题号硬刷专题14的题量不小如果从头到尾按顺序硬刷很容易在前面几道偏数学证明的题上卡太久心态会崩。我个人的建议是把它按知识块拆成几组每一组内集中刷完再进下一组知识块核心考点建议用时质数与筛法素数判定、埃氏筛、线性筛、区间筛2-3 天欧拉函数单点 phi、筛 phi、欧拉定理2 天快速幂与取模快速幂、快速乘、费马小定理求逆元1-2 天exgcd 与同余不定方程、同余方程、逆元3 天中国剩余定理基础 CRT、扩展 CRT2 天组合数取模阶乘预处理、逆元预处理、卢卡斯定理2-3 天每组题目之间并不孤立。比如求逆元那组会用到 exgcd 和费马小定理组合数取模那组又会用到快速幂和逆元。按块刷的好处是你刷完一组之后能立刻知道这类题长什么样建立“知识点到题型”的映射。做每道题之前我给自己定了一条规矩至少独立思考 30 分钟。30 分钟不是死规定但如果一道题我连一点思路都没有说明问题不是“没灵感”而是这个知识点还没有真正理解这时候看题解是最高效的。看题解之后一定要合上题解自己重新写一遍代码不能边看边抄否则下次碰到还是不会。3.2 拿一道典型题走一遍完整流程拿“求 a 关于模 n 的乘法逆元”这道最经典的题举例。看到题目第一反应应该是列式子找一个 x 使得 ax ≡ 1 (mod n)。如果你只知道暴力就会枚举 x 从 1 到 n-1复杂度 O(n)。当 a 和 n 到 1e9 级别时直接超时。这时候开始想同余方程 ax ≡ 1 (mod n) 等价于 ax ny 1这是一个标准的二元一次方程。从数学上想只有当 gcd(a, n) 1 时才有解这正好是逆元存在的条件。于是进入 exgcd 套路调用exgcd(a, n, x, y)得到一组特解再把它调整成最小正整数解(x % n n) % n。整个过程的三步——建立同余方程、判断 gcd、调用 exgcd——就是专题14里所有逆元题的标准路径。我自己做这类题时的复盘笔记长这样知识点是 exgcd 求逆元卡住的环节是忘记对 gcd 判断非 1 时无解题解里的关键转化是“同余方程改写成不定方程”下次遇到同余问题先想能不能转成 ax by c 的形式。这种复盘不复杂但能让你把每道题的收获留在脑子里而不是刷完就忘。3.3 整理一份“数论错题本”的方法刷题很容易陷入“AC 了就是会了”的错觉。数论题尤其需要错题本因为它的错法非常集中有人总在取模上爆负数有人把费马小定理用在非质数模数上有人 CRT 忘记乘逆元。这些错第一次犯很正常第二次再犯就是亏。我的错题本只要四列题目简述卡住的环节题解关键下次怎么识别求逆元用了费马小定理但模数不是质数换 exgcd看到模数不保证质数时优先 exgcdCRT 模板题忘了乘逆元每个 Mi 都要乘以对应逆元再求和用 M15 的小例子验证区间筛直接开大数组 MLE只用 sqrt 以内质数标记区间看到 L,R 很大但 R-L 小的字眼错题本不用写得很长重点是记录“为什么当时没想出来”。很多数论题不是你不会定理而是没识别出该用哪条定理。把这些识别信号记下来比重复刷十道题有用得多。4. 常见问题与排查技巧4.1 取模负数与溢出C 里负数取模的结果是负的比如-5 % 3 -2。很多数论题求的是最小正整数解最后如果不处理负数就 WA。统一格式int mod(int x, int m) { return (x % m m) % m; }这个(x % m m) % m是处理负数的标准写法适用于所有需要把结果归到 [0, m) 区间的场景。溢出的场景更隐蔽。假设两个小于 1e9 的数相乘int 直接溢出long long 在大多数情况下够用但模数接近 1e18 时就危险。除了用__int128硬扛更通用的写法是快速乘long long mul_mod(long long a, long long b, long long mod) { long long res 0; while (b) { if (b 1) res (res a) % mod; a (a * 2) % mod; b 1; } return res; }不要觉得这种写法慢它在模数超过 int 范围的题里就是保命符。我一般把快速乘和快速幂放一起封装用的时候直接换。4.2 用错逆元求法求逆元有三种主流方法很多人一开始只会一种遇到特殊场景就卡住。这里直接对比方法前提条件复杂度适用场景费马小定理模数为质数O(log mod)模数固定 1e97比赛最常用扩展欧几里得gcd(a, mod) 1O(log a)模数不保证质数通用性最强线性递推同样模数下批量求逆元O(n)预处理 1 到 n 的逆元表不少人一上来看到qpow(a, mod-2, mod)就直接背下来但没意识到这里用到了费马小定理前提条件是 mod 必须是质数。如果题目里模数是 1000000007 这种固定大质数没问题一旦模数是输入的变量就必须改成 exgcd 或者先判断质数。专题14里至少有一道题专门卡这个点我当时连续 WA 了三次才发现模数根本不是质数。4.3 边界条件反复挂数论题的边界值看着简单但特别容易挂。我整理了一个每次提交前默念的清单n 1 时欧拉函数是 1素数列表为空很多筛法没初始化会出问题。快速幂指数为 0 时结果应该是 1 mod p当 p 1 时为 0。CRT 算出来的解可能是负数记得最后取正。区间筛中 L 1 时1 不是质数要单独标记为合数。求约数个数时注意 n p^a 这种只有一个质因子的情况公式里的加一别漏。这些边界不是靠智商规避的是踩坑踩出来的。第一次做数论题就把这些情况全部标进错题本后面会省下大量调试时间。4.4 调试数论题的对拍技巧数论题特别适合对拍因为暴力解通常都很容易写。比如验证欧拉函数单点求法的正确性可以写一个 O(n) 的暴力去数互质个数然后拿它和正式代码跑同一个小数据。我自己常用 Python 或者 C 做个对拍脚本随机生成 n比较两边的输出出错立刻定位。对拍脚本的次要作用是能帮你发现一些平时根本不会想到的输入。比如生成 n 1000000007 这种大质数或者 n 2^30 这种 2 的幂跑一遍就能看出代码在幂运算、边界上的小毛病。学习数论的过程中对拍是性价比最高的调试方式强烈建议每个人都熟练掌握。5. 刷完数论基础之后还能往哪走5.1 莫比乌斯反演从基础到计数的下一步刷完专题14之后我想推荐的下一个方向是莫比乌斯反演。它和欧拉函数、线性筛强相关用线性筛可以在 O(n) 内求出莫比乌斯函数 mu然后通过容斥原理解决形如“1 到 n 中与 m 互质的数有多少个”的计数问题。最开始看莫比乌斯反演会觉得是一堆玄学公式但实际上它可以理解成在因数结构上做容斥。专题14里已经有几道题在雏形上沾到了莫比乌斯函数的边比如统计 gcd 为 1 的数对数量。先把线性筛求 mu 的代码写出来再去理解反演公式会顺畅很多。5.2 数论分块O(n) 变 O(sqrt(n))另一件值得学的事是数论分块。它解决形如 Σ floor(n/i) 的求和i 从 1 到 n。直接累加是 O(n)对大数据直接超时但你会发现 floor(n/i) 的取值是一段一段相同的每一段可以一起算总复杂度降到 O(sqrt(n))。这个技巧在后面的除数函数求和、莫比乌斯计数题中出现频率极高而且代码短到不可思议。我会建议在刷完专题14后花一个下午专门练数论分块它几乎是数论进阶里最“性价比高”的算法。5.3 再往后离散对数、原根、NTT如果还想继续往上走方向不外乎这几个离散对数算法、阶与原根、二次剩余、多项式相关的数论变换。这些都是专题14的延伸比如离散对数问题本质上是在群里求指数和快速幂是反向操作NTT 则是把数论取模和多项式卷积结合的大型考点。但说实话这些内容不需要在没刷完基础之前去碰。数论基础就像一个房子的地基房子的样子可以是任意风格但地基不牢固后面学什么都摇摇晃晃。先把专题14踏踏实实刷完让线性筛、欧拉函数、exgcd、CRT 这几根柱子立稳再往上层加东西那才是效率最高的路线。我自己的实际体会是数论不是靠背公式能学好的一定要亲手推几个例子。专题14刷到一半的时候我才真正理解 exgcd 递归返回的 x 和 y 是怎么一路被“换”回来的那一刻的感觉比 AC 一道难题还舒爽。这篇文章里写出来的坑我基本都踩过一轮希望你能绕开更快走到顿悟的节点。
