数论基础学习路线：从快速幂到中国剩余定理的实战指南

很多刷算法题的人一听到数论两个字就头疼总觉得一堆定理绕来绕去学了也不知道能不能拿分。我前前后后把《算法竞赛入门经典》第十章数学部分和kuangbin专题14数论基础刷了两遍一个很直观的感受是数论基础反而是性价比最高的模块。它的知识点边界非常清楚套路高度固定只要你把模运算、扩展欧几里得、逆元、中国剩余定理、欧拉函数、素数筛这几块吃透题单里八成题目都能稳定得分。这篇文章不打算简单罗列题单而是把我从看书、推导、刷题到踩坑复盘的全过程拆开讲。内容包括紫书第十章和专题14分别解决什么问题、六个核心知识点的推导与模板、三周的刷题节奏安排以及我实测下来最容易翻车的十几个坑。不管你是刚开始接触算法的学生还是想系统补数论基础的开发者照着这条路线走基本不会迷路。1. 为什么紫书第10章要和数论基础专题一起刷1.1 紫书第10章把数学概念串成一条线《算法竞赛入门经典》这本书在圈子里被叫做紫书大家平时打字图省事经常打成紫薯叫着叫着就顺口了。它的第十章标题是数学概念与方法是整个教材里唯一集中讲数学的一章。这一章的定位不是题典而是帮你把散落的知识点建立成体系先是同余、模运算、欧几里得算法再到扩展欧几里得、模线性方程、快速幂然后是计数、概率、递推等内容。我特别看重这一章的地方在于它对每个定理都给了推导过程和例题分析。比如扩展欧几里得为什么能反推出 x、y 的解模线性方程什么条件下有解、解有多少个书中都讲得很细。这些东西如果只背模板遇到变体题必死但如果你盯着推导看一遍很多题目一眼就能看出在考什么。不过紫书第十章也有明显的短板例题太少。每个知识点后面通常只有一两道带分析的例题想靠一本书达到熟练解题的程度远远不够。这时候就需要一个足够规模的题单补上实战这一环。1.2 kuangbin专题14一套难度递进的实战题库kuangbin专题是网上流传很久的一套分专题训练题单把算法竞赛常见知识点拆成了几十个专题。专题14叫数论基础题量大约三四十道覆盖了扩展欧几里得、线性同余、中国剩余定理、欧拉函数、素数判定与筛法、质因数分解、容斥原理、离散对数等多个方向。这个题单最大的特点有两个。第一个是循序渐进前面的题基本就是套模板比如快速幂、单个欧拉函数给你练手建立信心中间的题开始需要你会推导比如解同余方程、求大区间内的素数后面的题则是多知识点组合比如欧拉函数和容斥结合、质因数分解和等比数列求和结合。第二个特点是数据范围普遍不温柔动不动就是几十亿、几百亿的区间逼着你考虑复杂度和溢出问题而不是把循环写出来就完事。对大多数人来说光看书不会做题光刷题又不知道自己在学什么。把紫书第十章和这个专题搭配起来刚好形成理论加推导加实战加复盘的完整闭环。1.3 两套资料的互补点在哪我的经验是学习顺序上先看书、再刷题、刷完回来再看书效果最好。具体说看书阶段只求理解不要求AC。把每个定理的适用条件、推导过程过一遍重点标注那些什么时候能用、什么时候不能用。刷题阶段每道题先想清楚它对应哪个知识块再动手。如果一道题卡了半小时以上回去翻书的对应小节往往会有豁然开朗的感觉。复盘阶段把做错的题整理成自己的错误清单再回到书里找导致错误的原理漏洞。紫书第十章里的数学推导能帮你理解题单里那些为什么可以这么做题单的题目又会反过来检验你是不是真的理解了。只刷题不看书的人通常会记住模板但不会变通只看书不刷题的人上了考场会发现手生得厉害。两样配合才是性价比最高的用法。2. 数论基础六大核心知识点逐个拆给你看2.1 模运算与快速幂一切数论题的入场券数论题九成以上最后都会落到求某个数对 mod 取模上所以模运算的规则必须刻在脑子里。基本性质大家都会真正容易翻车的是两点第一是负数取模。在主流编译器里负整数取模的结果可能是负数所以凡是可能出现负数的表达式最后都要统一写成(val % mod mod) % mod把它变成数学意义上的非负余数。第二是乘法溢出。long long 的取值范围大约到 9.2e18当 mod 本身接近 1e18或者计算 a * b % m 时 a、b 都很大直接乘就会溢出。解决办法是用快速乘或者用 __int128 中间过渡后者在 Linux 环境的 g 下可用但使用前要确认评测环境是否支持。快速幂的原理是二进制拆分把指数 b 看成二进制每一位对应 a 的某个 2 的幂次累乘上去。复杂度从 O(b) 降到了 O(log b)这是数论题最基础的优化没有它指数稍微大一点就彻底没法做。long long qpow(long long a, long long b, long long mod) { long long res 1 % mod; while (b 0) { if (b 1) res res * a % mod; a a * a % mod; b 1; } return res; }快速乘的写法和快速幂几乎一模一样只是把乘法换成加法long long qmul(long long a, long long b, long long mod) { long long res 0; while (b 0) { if (b 1) res (res a) % mod; a (a a) % mod; b 1; } return res; }注意 res 的初始值快速幂里写成1 % mod是为了兼容 mod 1 这种边界情况快速乘里则从 0 开始累加。这两个细节平时不起眼遇到极端数据时能救命。2.2 扩展欧几里得解方程、求逆元全靠它欧几里得算法就是辗转相除求最大公约数核心是 gcd(a, b) gcd(b, a % b)复杂度 O(log n)。真正有杀伤力的是它的扩展版本不仅能求出 gcd(a, b)还能找到一组整数 x、y满足 ax by gcd(a, b)。这个等式看起来抽象用途却广得吓人求乘法逆元、解模线性方程、解二元一次不定方程、解中国剩余定理里的关键一步全都要用到它。理解它的关键在于递归返回时反推递归到 b 0 时显然有 x 1、y 0得到 a1 00 a回溯时把上一层的解带回去就能整理出这一层的 x、y。long long exgcd(long long a, long long b, long long x, long long y) { if (b 0) { x 1; y 0; return a; } long long d exgcd(b, a % b, y, x); y - a / b * x; return d; }这里一定要理解一个细节递归调用时参数顺序是exgcd(b, a % b, y, x)把这一层的 y 传给递归的 x把 x 传给递归的 y回溯回来之后 x 和 y 刚好满足上一层等式关系最后再根据 a b * (a/b) a % b 的恒等式调整 y。如果没搞懂这个推导就只能背一份魔改模板遇到系数为负数的题很容易算出错的解。另外exgcd 解出来的 x 不唯一所有解可以写成 x k * (b/g) 的形式。做题时经常需要把解归到某个范围通用写法是(x % (b/g) b/g) % (b/g)这个归一化操作在后面解同余方程时会反复用到。2.3 乘法逆元三种求法各有什么适用场景逆元的定义很简单如果 a * inv ≡ 1 (mod m)就说 inv 是 a 在模 m 下的乘法逆元。为什么需要它因为模运算下不能直接做除法a / b (mod m) 要改写成 a * inv(b) (mod m)。逆元存在的充要条件是 gcd(a, m) 1这一点必须时刻记住很多人做不出题就是因为模数和除数不互质时依然强求逆元。求逆元有三种常用方法第一种是费马小定理只适用于 m 是素数的情况直接inv(a) qpow(a, m-2, m)因为 a^(m-1) ≡ 1 (mod m)。这是比赛里最省事的方法但前提不能搞错。第二种是扩展欧几里得适用于任意模数只要 gcd(a, m) 1调用 exgcd(a, m, x, y)得到的 x 再归一化就是逆元。第三种是线性预处理当题目需要求 1 到 n 所有数的逆元且 m 是素数时用递推公式 O(n) 一次算完inv[1] 1; for (int i 2; i n; i) inv[i] (m - m / i) * inv[m % i] % m;这个递推公式看着奇怪推导其实不复杂设 m ki r其中 k m/ir m%i两边对 m 取模得到 ki r ≡ 0两边同乘 inv(i) * inv(r)就得到 k * inv(r) inv(i) ≡ 0于是 inv(i) -k * inv(r) ≡ (m - m/i) * inv[r] (mod m)。写代码时注意中间的乘法结果可能超过 int 范围建议全部用 long long 运算。2.4 中国剩余定理合数模数的一揽子方案中国剩余定理解决的是形如x 除以 m1 余 a1除以 m2 余 a2……的一组同余方程组前提是所有的模数 m1, m2, ... 两两互质。做法很机械先算 M m1 * m2 * ... * mk对每个 i 计算 Mi M / mi再求 Mi 在模 mi 下的逆元 ti最后 x Σ(ai * Mi * ti) mod M。long long crt(vectorlong long a, vectorlong long m) { long long M 1, ans 0; for (long long v : m) M * v; for (int i 0; i (int)a.size(); i) { long long Mi M / m[i]; long long x, y; exgcd(Mi, m[i], x, y); x (x % m[i] m[i]) % m[i]; ans (ans a[i] * Mi % M * x) % M; } return (ans % M M) % M; }为什么每个 Mi 要乘逆元因为 Mi 跟除了 mi 以外的所有模数都互质所以在其他模数下 Mi ≡ 0而在模 mi 下Mi * ti ≡ 1乘以 ai 后ai * Mi * ti 就满足对 mi 取模等于 ai对其他模数取模等于 0。把所有项加起来每一项各管一个方程互不干扰。真正麻烦的是模数不互质的情况。此时标准 CRT 不适用需要用合并同余方程的办法每次拿两个方程 x ≡ a1 (mod m1)、x ≡ a2 (mod m2)写成 x a1 m1 * t代入第二个方程得 m1 * t ≡ a2 - a1 (mod m2)用扩展欧几里得判断是否有解并求出 t然后合并成新的方程 x ≡ a1 m1*t (mod lcm(m1, m2))。这个过程做 k-1 次就得到最终解。这一块是专题里最容易卡人的点之一我建议把合并逻辑单独封装成一个函数多找几道题练熟。2.5 欧拉函数统计互质个数的万能钥匙欧拉函数 φ(n) 表示小于等于 n 且与 n 互质的正整数个数。它的计算方法是质因数分解后套公式φ(n) n * Π(1 - 1/p)其中 p 遍历 n 的所有不同质因子。比如 φ(12)12 2^2 * 3所以 φ(12) 12 * (1 - 1/2) * (1 - 1/3) 4。单个数求欧拉函数用试除法就能做到 O(sqrt(n))但专题里有很多题要求一次性算 1 到 n 的所有 φ(i)这时就得用线性筛预处理复杂度 O(n)每个合数只被它的最小质因子筛掉一次同时在筛的过程中顺便算出 φ。void euler_sieve(int n) { phi[1] 1; for (int i 2; i n; i) { if (!vis[i]) { prime[tot] i; phi[i] i - 1; } for (int j 1; j tot i * prime[j] n; j) { vis[i * prime[j]] 1; if (i % prime[j] 0) { phi[i * prime[j]] phi[i] * prime[j]; break; } else { phi[i * prime[j]] phi[i] * (prime[j] - 1); } } } }这段代码里最值得琢磨的是if (i % prime[j] 0)那行。它保证每个合数只被最小质因子筛一次是线性的关键同时 phi 的两种递推方式正好对应prime[j] 是否已经在 i 中出现过两种情况。如果只背代码不理解这一行遇到数据范围稍大的题就容易超时或者出错。欧拉定理是欧拉函数的直接应用如果 gcd(a, m) 1那么 a^φ(m) ≡ 1 (mod m)。当 m 是素数 p 时φ(p) p - 1就退化成费马小定理。这两个定理除了用来求逆元还有一个重要用途当指数 b 非常大时可以用降幂公式把指数先取模再计算。专题里确实有指数给到几十位的题不做这一步快速幂再快也没用。2.6 素数筛与质因数分解打表是数论的基本功素数相关的题在数论基础里占比不小最常用的两个工具是埃氏筛和线性筛。埃氏筛写法简单从 2 开始把每个素数的倍数全部标记为合数复杂度 O(n log log n)n 在一两百万以内完全够用。线性筛如上面代码所示每个合数只标记一次n 可以到一千万量级而且能顺便求欧拉函数属于必须掌握的进阶姿势。还有一个优化细节埃氏筛里从 p*p 开始枚举可以省掉大量重复标记这个优化虽小n 很大时却能省不少时间。质因数分解最朴素的办法是试除法从 2 枚举到 sqrt(n)能整除就除到底。这里有个实用技巧循环结束后如果 n 还大于 1剩下的 n 本身就是一个质因子不要漏掉。我见过很多新手在循环里把 n 除成 1 就结束了却忘了处理最后那个大于 sqrt 的质因子答案差得离谱。区间筛是另一个经常考到的点要求 [L, R] 区间内的素数其中 R 可以达到 2^31 甚至更大但 R - L 只有十几万。此时不能直接开一个 R 大小的数组正确做法是先用普通筛法筛出 [2, sqrt(R)] 内的所有素数再用这些素数去标记 [L, R] 区间内的合数。void segment_sieve(long long L, long long R) { for (long long i L; i R; i) is_prime[i - L] 1; for (long long p 2; p * p R; p) { if (!is_small_prime[p]) continue; long long st max(2LL, (L p - 1) / p) * p; for (long long j st; j R; j p) is_prime[j - L] 0; } if (L 1) is_prime[0] 0; }起始位置的计算是区间筛的灵魂(L p - 1) / p是 L 除以 p 的上取整乘回 p 就是不小于 L 的最小 p 的倍数再和 p*p 取较大者避免把小于 p 的数重复标记。别看就这么一行表达式区间筛八成以上的 bug 都出在这里建议多手算几组数据确认。3. 实操过程从推导到AC的完整复盘3.1 先把几个核心模板打磨成顺手的样子刷题之前我建议先把上述核心算法整理成自己的模板库每个模板都要能默写。注意默写和背诵是两回事默写是指你理解每一行在干什么能现场推出来背诵只是 CtrlC/V 的肌肉记忆。前者遇到变体题能活后者遇到变体题就死。我自己的模板库大概长这样qpow / qmul快速幂、快速乘各一份注意 long long 和取模边界。exgcd求解 ax by gcd(a, b)返回 gcd 并输出一组解。get_inv(a, m)先判断 gcd(a, m) 1再用 exgcd 或费马小定理。crt标准 CRT 和不互质合并两个版本分开写。euler_sieve线性筛同时求 phi 数组。segment_sieve区间筛模板。每个模板下面我还写几行注释记录它的适用条件。比如 get_inv 旁边一定写着前提 gcd(a,m)1m 为素数时可用费马小定理crt 旁边写着模数两两互质用标准 CRT否则用合并法。这些注释在比赛时比代码本身更值钱因为紧张状态下人最容易忘记的就是前提条件。3.2 用三道经典题把理论串起来我拿三道能覆盖大部分知识点的题目讲一讲从读题到 AC 的完整思路题目描述我就不完整复述了重点是建模和推导过程。第一道是青蛙绕圈相遇类问题。两只青蛙在同一条环形路上跳初始位置不同、速度不同问跳多少步之后相遇。建模之后就是解 (m-n) * t ≡ (y-x) (mod L)。这类题的套路是先写出同余方程令 a (m-n) % Lc (y-x) % Ld gcd(a, L)如果 c % d ! 0直接判定无解否则方程两边同时除以 d变成 a * t ≡ c (mod L)用 exgcd 求出一组解再乘上 c 并对 L 取模归一化。核心是理解除以 d 之后模数也要跟着变并且最后得到的解是模 L 意义下的而不是模 L。第二道是求 A^B 的所有约数之和。先质因数分解 A p1^a1 * p2^a2 * ...那么 A^B 的约数之和等于每个质因子方向上的等比数列乘积Π(1 pi pi^2 ... pi^(ai*B))。难点在于等比数列求和时不能直接套 (p^(n1) - 1) / (p - 1) 的公式因为模数不保证是质数p - 1 未必有逆元除法没法做。正确做法是用二分递归把等比数列拆成两半前半部分加上后半部分的公因子就能递归求解。这个技巧在专题里出现过不止一次一定要练熟。第三道是统计 n 以内与某个集合都互质的数的个数。最朴素的版本直接调欧拉函数就完了升级版是问 [1, r] 里有多少个数和集合里的所有数都互质这时候就要用容斥原理先质因数分解枚举这些质因子的所有子集按奇加偶减的原则计算。欧拉函数只适用于跟单个 n 互质而容斥可以处理跟多个数都互质的情况两者经常组合出现。3.3 三周刷题节奏安排表我建议用三周时间完成紫书第十章加专题14的第一轮每天保证两小时左右。具体节奏参考这张表阶段时间主要内容目标第一周第1-2天模运算、快速幂、快速乘能默写 qpow/qmul处理负数取模第一周第3-4天欧几里得、扩展欧几里得能独立推导 exgcd 回溯过程第一周第5-7天逆元三种求法、模线性方程同余方程都能解出归一化解第二周第8-9天中国剩余定理互质与不互质能写合并方程组代码第二周第10-11天线性筛、欧拉函数能一次筛出 phi 数组第二周第12-14天质因数分解、区间筛处理大区间素数问题第三周第15-17天容斥原理、等比数列求和完成组合类题目第三周第18-21天全真模拟限时做剩余题目每道题先判断知识块再动手这个节奏不要求每天做很多题关键是每个知识点都要保证至少三到五道题的量。做错的题不要急着看题解先回翻紫书对应小节自己找原因实在卡死再参考题解并把题解里的关键转化记进笔记。4. 常见问题与排查技巧实录4.1 溢出与负数取模的坑数论题几乎就是溢出的重灾区。最常见的是快速幂里res * a % mod当 a 和 res 都接近 1e9 时乘积就是 1e18 量级long long 已经很吃力如果 mod 本身接近 1e18乘积必然溢出。我的习惯是凡是两个 long long 相乘再取模一律先评估要不要用快速乘或 __int128。__int128 在常见 Linux 评测环境下可用但有些环境会编译失败依赖它之前务必先确认。负数取模的另一个坑是解同余方程时得到的解可能是负数。记住统一公式(x % mod mod) % mod这是把编程语言里的向零取整变成数学意义上的非负取模最可靠的办法。我在刷专题时凡是减法、除法、模运算混在一起的地方都默认在最后套一遍这个归一化。4.2 逆元和除法取模的适用条件很多人在求等比数列和这类题上翻车根本原因是搞混了逆元的适用条件。逆元存在的充要条件是 gcd(a, m) 1。当模数是 1e97、998244353 这类素数时几乎所有数都有逆元可以放心用费马小定理但遇到合数模数时p - 1 很可能跟模数不互质直接套公式就爆了。我的建议是无论什么时候只要看到除法加取模先停下来想三秒——这个除数跟模数互质吗如果确定互质用逆元如果不确定或者不互质就改用二分递归求等比数列或者绕开除法。这个意识比会背十种模板都管用因为它直接决定了你的方法是否成立。4.3 筛法边界与数组大小的坑筛法的错误大多集中在边界。第一是数组下标越界用 is_prime[i - L] 做区间筛时一定要先确认 i 在 [L, R] 范围内再访问从 p 的倍数开始标记时如果 p*p 小于 L就要把起点抬到不小于 L 的最小 p 的倍数。第二是漏掉1 不是素数这个特判区间从 1 开始时is_prime[0] 必须手动置 0。第三是线性筛的内层循环条件 i * prime[j] n当 i 较大时 i * prime[j] 可能溢出 int所以这个比较最好改成长整型或者先判断 i n / prime[j]。还有一个容易被忽略的细节欧拉函数筛里约定 phi[1] 1但有些题目统计互质数时对 1 的处理并不统一。做题前仔细读题必要时用样例验证一下自己的公式是否包含 1。4.4 自己动手对拍的排查方法数论题出错时最有效的排查办法不是盯着代码看而是构造小数据对拍。我自己常用的流程是这样的先写一个足够直白的暴力版本比如直接枚举 1 到 1e6 验证筛法结果、用枚举验证逆元。随机生成几百组小数据跑暴力版和优化版比对输出。找到第一组不一致的数据手算一遍判断是优化版逻辑错了还是暴力版本身有边界问题。修正后重新对拍直到几千组数据全部一致。对拍代码本身很简单关键是暴力版要写得非常直白不要带上任何优化逻辑否则两边一起错还浑然不觉。这个方法帮我抓住了大量隐藏 bug比如区间筛起点算错、exgcd 返回负数解、CRT 合并时模数没跟着变等等。为了方便排查我把专题里出错较多的类型整理成了一张速查表症状可能原因排查方向结果偏大或偏小乘法溢出检查乘积是否超过 long long改用快速乘结果全为负数取模符号问题统一用 (x % m m) % m同余方程误判无解未先判断整除关系exgcd 前先算 gcd 并检查整除逆元结果错误误用费马小定理确认模数必须为素数CRT 答案错误模数不互质用合并法而非标准 CRT区间素数漏筛起点计算错误验证上取整表达式质因数分解漏因子未处理剩余部分循环结束后判断剩余值大于 15. 刷完基础阶段下一步往哪走5.1 进阶方向速览专题14和紫书第十章只是数论基础的入门。刷完之后你会发现自己的数论体系已经基本成型下一个阶段的进阶方向大致有这么几条第一是莫比乌斯函数与莫比乌斯反演它是数论里的大杀器很多 gcd 计数问题都可以化成整除关系配合整除分块可以处理超大范围的问题。第二是 BSGS 这类高阶算法用于解决离散对数问题专题结尾的几道题应该已经让你尝过苦头。第三是大整数分解与素性测试比如 Miller-Rabin 和 Pollard-Rho在数据范围动辄 1e18 的题目中非常有用。第四是积性函数体系的完整梳理欧拉函数只是积性函数里最简单的一个理解了线性筛筛积性函数的方法莫比乌斯函数、约数个数函数等等都能顺手搞定。这些进阶内容还是建议按老方法先看书找体系再找对应专题刷题最后复盘。有了基础篇打底进阶速度会快得多。5.2 给新手的几条实在建议最后分享几条我踩坑多年总结出来的实在建议。第一数论模板不要背要默写。每周挑一个固定时间把 qpow、exgcd、线性筛、CRT 这几个核心模板从头写一遍写错的地方就是你理解还不到位的地方。第二做题先判定知识块再动手。拿到一道数论题第一件事不是写代码而是问自己这题考的是同余方程、欧拉函数、筛法、还是容斥想清楚再动手正确率和速度都会明显提升。第三所有除法取模都必须先验证互质性这是最容易出问题也最容易预防的一步。第四像收集卡片一样收集反例。每次做错一道题把错误模式记下来比如没先判断能否整除区间筛起点少加了 p下次遇到同类题先扫一眼错误清单。我个人体会最深的一点是数论基础这套东西学的时候觉得又散又抽象但一旦你把这些知识点串成网后面遇到任何算法题里的数学环节都会觉得轻车熟路。紫书第十章的推导给你体系专题14的题目给你手感两样缺一样都会事倍功半。如果你正卡在这个阶段别急着求快把每一道题都当成一次推导练习三周之后再回头看你会对数论有一个完全不一样的感受。