1. 数论与组合计数为什么这两个专题值得单独拎出来讲数论和组合计数严格来说是两门独立的数学分支。数论研究整数本身的规律组合计数研究“到底有多少种可能”。但任何一个系统的数学学习计划几乎都把这两个话题放在相邻位置很多竞赛题、笔试题、进阶考试里它们也经常结伴出现。原因很朴素数论里的同余、剩余类、素数分布本质上就是在给整数做“分类和计数”而组合计数里很多问题算到最后又离不开同余去处理大数取模、验证结果。两者是互相喂养的关系拆开学反而容易学成两张皮。这个专题适合三类人。第一类是备战数学竞赛或各类选拔考试的学生数论和组合是出题频率最高的两块第二类是准备计算机方向笔试面试的开发者很多算法题背后的数学内核就是这两个分支第三类是单纯想补一补数学底子、找回手感的人。这篇文章不按教科书那套“定义—定理—证明”的顺序来而是按“工具—用法—实战—避坑”推进。每个结论我都会把背后的为什么讲清楚再给到可以直接套用的步骤。你先别急着背公式先把思路捋顺做题只是顺便的事。2. 数论的核心工具整除、同余与素数2.1 整除与最大公约数一切推理的起点数论的所有问题几乎都从整除开始。所谓 a 整除 b通俗说就是 b 除以 a 余数为 0记作 a | b。这个定义简单但真正用起来有很多容易被忽略的细节。比如“0 能不能被整除”“负数能不能参与整除”这类边界问题教科书里往往一笔带过实际做题时却经常让人卡壳。我的习惯是严格按定义走整除只要求存在整数 k 使得 b ka所以负数完全合法但除数不能为 0否则没有意义。整除之后紧接着就是最大公约数记作 gcd(a, b)。这是数论里出现频率最高的概念没有之一。计算最大公约数永远推荐辗转相除法也叫欧几里得算法而不是去分解质因数。原因很实际两个 10 位以上的数分解质因数可能要把人算崩溃但辗转相除法只需要几次除法就能出结果。它的原理其实一句话就能说清gcd(a, b) gcd(b, a mod b)。每次把大数换成余数数字迅速变小几轮之后余数为 0此时的除数就是答案。我在实际教学中发现很多人会背辗转相除的步骤却不理解为什么余数能替换原来的数。这里给一个直观解释如果 d 同时整除 a 和 b那么 d 一定能整除 a - kb也就是余数 r。反过来如果 d 同时整除 b 和 r那么 d 也一定能整除 a。所以 a 和 b 的公约数集合与 b 和 r 的公约数集合完全一样最大公约数自然也不变。理解了这一层你就不容易在套算法时出错也更容易记住它的变体——扩展欧几里得算法后者用来解同余方程和线性方程特别有用。2.2 同余把无限问题装进有限盒子同余的概念是数论真正开始“有用”的地方。说 a 和 b 对模 m 同余记作 a ≡ b (mod m)意思是 a - b 能被 m 整除或者说 a 和 b 除以 m 的余数相同。这个记号最厉害的地方在于它把无穷多个整数归成了 m 个类每个类里的数在模 m 意义下“地位相等”。这就把无限问题变成了有限问题。同余的运算规则跟等式很像两边可以同时加、减、乘同一个数同余关系不变。但有一个非常关键的例外——除法。等式两边可以同时除以一个非零数同余却不能随便除。比如 2 ≡ 12 (mod 10)两边除以 2 得到 1 ≡ 6 (mod 10)显然是错的。只有当除数和模数互质时才可以做除法或者说要做除法必须乘以除数的“逆元”。这个“除法不能乱用”的坑几乎每个初学者都会踩我后面还会专门讲。同余在实际计算中最常用的场景是求余数。比如算 12345 × 6789 除以 7 的余数不需要先算出乘积再除而是分别算 12345 除以 7 的余数再算 6789 除以 7 的余数两个余数相乘后再取余。因为乘法对同余是封闭的每一步都能把数字控制在很小范围内。这就是“边算边取模”的思路写程序的人对这个应该特别熟悉。2.3 素数判断、分解与筛法素数在数论里的地位不用多说它是整数乘法意义上的“原子”。判断一个数是不是素数最朴素的办法是从 2 试除到根号 n。很多人不明白为什么只需要试到根号 n其实道理很简单如果 n 有一个大于根号 n 的因子那么必然存在一个小于根号 n 的因子与之配对所以你只需要检查小的那一半就够了。这个结论虽然基础但它是很多判断算法效率分析的核心。真正遇到大规模判断素数时试除法就不够用了。这里我推荐先掌握埃拉托斯特尼筛法思路是把从 2 开始的每个素数的倍数全部标记为合数剩下的就是素数。它适合一次性求出一段范围内所有的素数比如说求出 100 万以内的所有素数用筛法在普通电脑上瞬间就能完成。筛法里有个小细节很多人没注意开始筛 p 的倍数时应该从 p² 开始而不是从 2p 开始因为小于 p² 的倍数一定已经被更小的素数筛过了。这个小优化能让筛法效率明显提升写代码的时候值得用上。至于质因数分解那是另一个层面的问题。小数字分解靠试除就行大数字分解到现在也没有多项式时间的经典算法很多加密系统的安全性本质上就建立在“大数难分解”这件事上。不过作为数学专题的学习者你要掌握的是一种感觉分解不光是拿到几个素因子更重要的是能把一个数的约数个数、约数和、欧拉函数等一系列性质都算出来这些才是出题人真正想考的东西。2.4 费马小定理与欧拉定理指数运算的加速器费马小定理是数论里最优雅的一个结论如果 p 是素数a 不是 p 的倍数那么 a 的 p - 1 次方模 p 等于 1。它的证明用到了组合计数里的一个经典结论——剩余类的循环置换这也是两个专题交叉的一个典型例子。这个定理最大的实用价值是化简大指数要算 a 的 2023 次方模 13不需要真的去乘 2023 次直接看 2023 除以 12 的余数把指数降到余数那么大就够了。欧拉定理是费马小定理的推广把素数 p 换成任意正整数 m把 p - 1 换成欧拉函数 φ(m)结论同样成立。这里的 φ(m) 表示 1 到 m 之间与 m 互质的整数个数。为什么要学习这个推广因为实际题目里模数往往不是素数比如模 100、模 2023 都是合数这时候费马小定理就失效了必须用欧拉定理。计算欧拉函数本身也是一类经典问题如果 m 分解成素因子乘积那么 φ(m) m × (1 - 1/p₁) × (1 - 1/p₂) × …这个公式建议记牢出题频率非常高。需要特别注意的是欧拉定理和费马小定理都有“a 与模数互质”的前提。如果 a 和模数不互质这两个定理都不能直接使用。很多题目故意在这个地方挖坑让你看着条件很像却用错。我个人处理这类问题的方法是先判断底数和模数是否互质不互质就退回同余的基本运算或者单独处理公因子的那部分。3. 组合计数的底层逻辑从数数到建模3.1 加法原理与乘法原理两个最朴素却最容易被用错的规则组合计数的地基是两个几乎不用证明的规则。加法原理说如果一件事有 A 类和 B 类两种互不重叠的做法A 类有 m 种B 类有 n 种那一共就有 m n 种。乘法原理说如果一件事分成两步第一步有 m 种选择第二步有 n 种选择那一共就有 m × n 种。听起来像废话但真正做题时这两个规则的误用率极高。最常见的错误是“分类没分干净”。用加法原理时各类之间必须互斥不能有交叉。比如“选一个既会跳舞又会唱歌的人”和“选一个只会跳舞的人”这两类就有重叠直接相加会把重叠部分算两遍。另一个常见错误是把乘法原理套在依赖关系上第一步选了某个选项之后第二步的可选项数会变化这时候直接相乘就错了。正确的做法是先处理有特殊限制的步骤或者用排列公式一步到位。我个人的经验是拿到一个计数问题先问自己三句话这件事是分几类完成的还是分几步完成的分类之间有没有重叠每步的选择数是否受前面步骤影响这三句话能过滤掉至少一半的低级错误。3.2 排列与组合选完还要不要排序排列和组合是计数公式的核心。从 n 个不同元素里选 k 个排成一列叫排列数量是 P(n, k) n! / (n - k)!只选出来不管顺序叫组合数量是 C(n, k) n! / [k! × (n - k)!]。两者唯一区别就是“选完之后要不要排序”。这个区分听起来简单但实际题目里“顺序到底算不算重要”经常是隐性的。我给学生的判断标准是把选出来的元素交换一下位置如果得到的是不同的结果那就是排列问题如果还是同一种结果那就是组合问题。比如从 5 个人里选 3 个去领奖同一个人的集合谁领一等奖谁是二等奖结果完全不同这是排列从 5 个人里选 3 个组成一个委员会委员会成员之间的位置没有差别这是组合。还有一个高频考点是“相邻”和“不相邻”的处理。相邻元素要“捆绑”成一个整体参与排列再乘内部排列数不相邻元素则通常“先排其他元素再往空隙里插”。这里有个细节容易漏n 个元素排成一排有 n 1 个空隙含两端但两个相邻元素之间不能插所以实际上是先排好其他元素制造空隙再逐个安排位置。捆绑法的核心是别忘了解绑后的内部排序插空法的核心是别忽略两端的空隙。3.3 容斥原理用“减”来算“加”容斥原理是处理“至少满足某条件”或“不满足任何条件”问题的利器。最常见的形式是|A ∪ B| |A| |B| - |A ∩ B|两个集合的并集等于各自大小之和减去重合部分。三个集合时变成 |A| |B| |C| - |A∩B| - |A∩C| - |B∩C| |A∩B∩C|加加减减交错进行。为什么最后要加回三者交集因为前面减掉两两交集时三个集合都重叠的那个部分被减了三次需要补回来一次。容斥原理看起来只是公式实际上它在组合计数里最强大的用法是用来算“一个都不满足”的数量。思路是先算出所有情况的总数再减去至少满足一个条件的情况。这个过程往往要先精确算出各个交集的大小交集越大越难算。我在做题时会先把所有集合的大小列成一张表标出两两交集再标出三三交集一层层往下填比直接背公式靠谱得多。容斥原理和数论的一个经典结合点是求一段范围内与某个数互质的整数个数。比如求 1 到 100 中与 30 互质的数有多少个可以先把 30 分解成 2、3、5 三个素因子然后用容斥原理减去 2 的倍数、3 的倍数、5 倍数的个数再加回两两相交的部分。这个思路在后面实战部分我会完整演示一遍它是两个专题交叉出题的代表作。3.4 插板法隔板分配与方程整数解插板法解决的是“把相同的东西分给不同的人”这类问题。经典模型是把 n 个完全相同的球分给 k 个人允许有人分不到有多少种分法答案是 C(n k - 1, k - 1)。很多人不理解这个公式怎么来的我用一个生活化的类比讲把 n 个球排成一排在它们之间的 n - 1 个空隙里插 k - 1 块隔板每块隔板隔开的部分就代表分给一个人的球数。但允许有人分不到时空隙就不够用了所以先给每个人预先“发”一个虚拟球这样问题就变成 n k 个球之间插 k - 1 块隔板得到 C(n k - 1, k - 1)。插板法的另一个常见形态是求正整数方程解的个数。比如 x₁ x₂ x₃ 10 的非负整数解有多少组等价于把 10 个相同的单位分给 3 个变量直接用公式 C(10 3 - 1, 3 - 1) C(12, 2) 66。如果题目要求每个变量至少是 1就先给每个变量减掉 1再套公式。我在教学时反复强调插板法只适用于“对象完全相同、盒子互不相同”的场景如果对象本身有不同的标签插板法就不适用了得回到排列的思路。3.5 递推用前面的结果算后面的结果很多组合计数问题没有直接的封闭公式但存在明显的递推关系。最经典的就是斐波那契数列F(n) F(n - 1) F(n - 2)。递推的价值在于把一个看起来无从下手的问题转化为“只关心前几步结果”的问题。比如上台阶问题每次可以跨 1 级或 2 级上 n 级台阶有多少种走法最后一步要么从 n - 1 级跨 1 级上来要么从 n - 2 级跨 2 级上来所以答案是两种更小规模的走法之和。这种“看最后一步怎么走”的思考方式是建立递推关系最通用的方法。递推的难点不在关系本身而在于初始条件的确定。F(1) 是多少F(2) 是多少必须验证到具体的小规模情形不能想当然。另一个常见陷阱是把递推方向搞反有些题目要求的是“至少”或“不超过”这时候直接递推容易漏状态需要重新设计状态定义比如把“到第 i 步时还剩 j 个名额”这种二维状态定义出来。我在做题时一定会把递推表列到前四到五项手工验算一遍确认没有逻辑漏洞之后再继续这个方法虽然笨但非常有效。4. 综合实战三组完整例题拆解4.1 求解同余方程接住第一个“除法陷阱”先看一道数论的基础题求解同余方程 5x ≡ 3 (mod 7)。这道题的常规解法是找一个数乘到 5x 左边让它变成 x。注意这里不能直接两边“除以 5”因为 5 在模 7 下的除法要先转化为乘以 5 的逆元。5 和 7 互质所以 5 在模 7 下一定有逆元。找逆元的办法是试5 × 1 55 × 2 10 ≡ 35 × 3 15 ≡ 1所以 5 的逆元是 3因为 5 × 3 ≡ 1 (mod 7)。两边同时乘以 3左边变成 15x ≡ x右边是 3 × 3 9 ≡ 2 (mod 7)。所以 x ≡ 2 (mod 7)即 x 2, 9, 16, …。这道题背后的逻辑值得说透。逆元存在的条件是“底数与模数互质”这一点和欧拉定理的前提完全一致因为本质上都是“可逆”的问题。如果不互质比如解 4x ≡ 2 (mod 6)就需要先约去公因子 2变成 2x ≡ 1 (mod 3)然后再解。很多同学一上来就套逆元公式发现解不出来就是因为没先做约分处理。遇到具体数字时用试除法找小逆元往往比背扩展欧几里得快数字大了再用扩展欧几里得。这个选择顺序是我实际做题总结出来的经验。4.2 字母重排里的捆绑与插空组合计数的一道经典题把单词“MATHEMATICS”的 11 个字母重新排列要求两个 T 必须相邻有多少种排法先处理字母重复M 出现 2 次A 出现 2 次T 出现 2 次其余字母 H、E、I、C、S 各 1 次。如果没有任何限制总数是 11! / (2! × 2! × 2!)除以 2! 是因为每个重复字母的互换不产生新排列。现在要求两个 T 相邻把这两个 T 捆成一个整体“TT”那么参与排列的是 10 个对象其中 M 重复 2 次、A 重复 2 次其他 6 个互不相同。排列数是 10! / (2! × 2!)。注意被捆进去的两个 T 内部没有额外的排列因为两个相同的 T 交换位置不产生新排列。这道题的坑在于有同学把两个 T 当作不同的元素内部乘了 2!结果答案翻倍这就是典型的“重复元素内部不做排列”的错误。再扩展一下如果题目改成“两个 T 不相邻”做法是先排除了 T 的 9 个字母再把两个 T 插到它们之间的 8 个空隙里也就是 C(8, 2) 种插法。为什么是 C(8, 2) 而不是先插一个再插一个因为两个 T 完全相同同时选两个位置即可不需要排序。这类题做多了就会发现捆绑和插空虽然是两种技巧但本质都在处理“特殊元素的位置关系”做题前先判断元素是否相同比急着套公式重要得多。4.3 数论与组合的交叉题1 到 200 中不能被 2、3、5 整除的有多少个这道题完美展示了两个专题怎么结合。先把问题转译成集合语言设全集是 1 到 200 的整数A 是 2 的倍数B 是 3 的倍数C 是 5 的倍数要求的是不在 A、B、C 任何一个集合里的数。用容斥原理|A ∪ B ∪ C| |A| |B| |C| - |A∩B| - |A∩C| - |B∩C| |A∩B∩C|。逐个算|A| ⌊200/2⌋ 100|B| ⌊200/3⌋ 66|C| ⌊200/5⌋ 40。两两交集分别是同时被 2 和 3 整除即被 6 整除⌊200/6⌋ 33被 2 和 5 整除即被 10 整除⌊200/10⌋ 20被 3 和 5 整除即被 15 整除⌊200/15⌋ 13。三者交集是同时被 2、3、5 整除即被 30 整除⌊200/30⌋ 6。代入公式100 66 40 - 33 - 20 - 13 6 146。所以能被 2、3、5 至少一个整除的有 146 个不能被任何一个整除的就是 200 - 146 54 个。算完之后我强烈建议你做一步验证直接把 1 到 30 这个小区间手写检查一遍看看不能被 2、3、5 整除的数有几个。我在手写时不查出来是 1, 7, 11, 13, 17, 19, 23, 29 这 8 个数。因为 200 除以 30 是 6 余 20所以 1 到 180 里有 6 × 8 48 个剩下 181 到 200 再单查能算出还有 6 个总数 54。这个“先算小区间再按周期扩展”的方法既是验证手段也是一种重要的数论思维——周期性。很多组合计数问题里的“周期重复”就是这么用的。5. 常见错误与排查方法实录5.1 数论部分的高频翻车点数论题的错误一般不是算错那么简单而是概念上的误用。第一个高频错误就是不检查互质条件就用费马小定理或逆元。我见过太多人在模数是合数时直接用 p - 1 当指数周期的结果答案差了十万八千里。我的习惯是动笔之前先用一句话标注前提底数和模数互质吗不互质的话要么分解处理要么退回同余定义慢慢算。第二个高频错误是同余除法乱用这个我在前面已经提过。第三个错误是欧拉函数算错尤其是合数分解这一步。算 φ(72) 时有人直接算 72 × (1 - 1/2) × (1 - 1/3)却忘了 72 2³ × 3²把分母约分时搞混。正确做法是先写标准分解式再用公式逐步代入每一步都保留分数形式最后再化简。这个细节虽然小但在竞赛和考试里就是 5 分和 0 分的区别。还有一个容易被忽略的坑负数取模。数学意义上的余数是 0 到 m - 1 之间的非负整数但很多计算工具和编程语言对负数取模的结果是负数或偏大的正数。做手算时遇到 -3 ≡ ? (mod 5)我会加上 5 得到 2。这个习惯在验证答案时非常重要否则你列出的结果可能看起来“对”但完全不在标准剩余类里。5.2 组合计数部分的高频翻车点组合题的最大翻车点是重复计数。具体表现有两种一种是分类时集合不互斥把同一个对象算进了多个类另一种是分步时没有考虑元素是否相同把重复元素的不同排列当成了新排列。我的排查方法是算完之后挑一个具体的计数结果把它对应的实际构造写出来看看有没有另外一套步骤产生同一个构造。如果存在说明你有重复计数需要除以前后步骤造成的置换数。第二个高频错误是忽略“至少”“至多”这类限制词。比如“至少选 1 个女生的方案数”有人直接用总数减去选 0 个女生的方案数这个思路是对的但有人会忘记“至少 1 个”包括“选 1 个、2 个、3 个”误以为只有一种情况。正确的做法是把“至少一个”的补集想清楚或者直接分情况讨论。第三种错误是排列组合符号混淆P 和 C 用错方向通常是因为没有先问“交换顺序是否产生新结果”。我在教学中还总结了一个“验算三件套”第一把小数字代入原题手工枚举一遍看看公式结果是否一致第二检查极端情况比如全部选、一个不选公式在端点是否成立第三如果题目有条件限制用补集思路再算一遍对比两次结果。这三步做完组合题的错误率能下降一大半。5.3 验证答案的实用手段除了手写验算写代码是验证组合计数和数论结论的高效手段。我通常在 Python 里写一个暴力枚举函数把题目描述直接翻译成循环用穷举得到正确答案再和我的公式结果对比。比如 1 到 200 中不能被 2、3、5 整除的数一行列表推导式就能算出来sum(1 for n in range(1, 201) if n % 2 and n % 3 and n % 5)运行结果是 54和手算的完全一致。这个方法适合思路卡壳时给自己一个确定性的参考。验证时还有一个容易踩的坑是“只验证了正确答案没验证错误过程”。比如你用容斥原理算出了 146再用补集算出了 54两者加回去等于 200这只是内部一致性检查不能证明思路本身是错的。更强力的验证是换个角度建模比如把容斥原理展开成逐项累加的方式把周期性验证放到 1 到 30 的区间上两种方法独立计算出同一个结果才能说明你的思路真的站得住脚。6. 学习顺序与几条过来人的建议如果你从零开始学这个专题我的建议顺序是这样的先花时间把整除、最大公约数、同余三个概念吃透它们是数论的工具箱然后学素数判断与筛法这时候结合一小部分组合计数里的容斥原理做几道互质计数题你会明显感觉到两个专题开始打通接着学排列组合的标准公式配合捆绑插空、插板法做专项练习再回头学费马小定理和欧拉定理你会发现前面组合计数的技巧在证明里也能派上用场。这个路线的好处是每个新知识点都能在前面的内容里找到落点不会学了就忘。练习量方面我不建议盲目刷题。数论每天做三四道就够关键是把每一道题的思路复盘一遍考了哪个定理前提条件是什么如果换了数字还能不能做。组合计数则需要多做几道因为它更依赖模型识别能力题目稍微换个说法就变成新题你要训练的是“这个题属于哪种模型”而不是背答案。我在带学生时反复强调一句话数论要靠精读组合要靠泛读两者训练方式不一样不要混为一谈。最后分享一个我自己用了很多年的习惯每学完一个定理自己出三道题考自己。一道直接套用一道改条件一道把定理反着用。比如学完费马小定理我给自己出的反问题就是“已知 a 模 p 的周期是 12能不能判断 p 大概是多少”。这种反推训练能逼你把定理的内在逻辑彻底想清楚效果比做十道常规题都好。数论和组合的奇妙之处就在于它们看似抽象却总能在意想不到的地方互相印证学得越深这种感觉越明显。