每年CSP-S提高组的数论题说穿了考的就是那么几板斧同余、逆元、扩展欧几里得、中国剩余定理。很多选手刷了一堆偏难怪题结果在同余方程这类最基础的知识点上栽了跟头——不是不会做是没想明白背后的原理。这篇文章我就顺着从同余到分数模运算这条线把同余方程这个实践环节彻底掰开揉碎用竞赛真题的套路带着你走一遍完整流程。适合那些已经学过模运算基本性质、但看到同余方程还是只能靠猜的选手也适合刚进提高组、想把数论地基打牢的同学。1. 同余方程从竞赛考点看它的真实面貌1.1 什么是同余方程先做个最简单的回忆。同余关系的定义是若 (a-b) 能被 (m) 整除则称 (a) 与 (b) 模 (m) 同余记作 (a \equiv b \pmod{m})。那同余方程长什么样典型形式是[ ax \equiv b \pmod{m} ]其中 (a, b, m) 是给定的整数(x) 是未知整数。这个方程的意思就是找所有整数 (x)使得 (ax-b) 是 (m) 的倍数。很多同学第一反应是把同余符号当等号用直接在两边做普通运算。这方向没错但有个关键区别同余方程的解在模 (m) 意义下可能不止一个。比如 (2x \equiv 2 \pmod{4})(x1) 和 (x3) 都满足因为 (2 \times 1 - 2 0)、(2 \times 3 - 2 4)都是 4 的倍数。所以解同余方程本质上是在研究解的集合长什么样。用生活化的方式理解这就像钟表上的时针。找到一个时刻 (x)使得时针走了 (ax) 小时之后停在 (b) 这个刻度上。钟表只有 12 个刻度所以每隔一圈就重复一次解的个数自然可能不止一个。理解了这个场景后面各种性质就好办多了。1.2 解存在的条件和解的数量先判断有没有再看有几个解同余方程的第一件事不是急着求 (x)而是先判断方程到底有没有解。这里有一个决定性定理同余方程 (ax \equiv b \pmod{m}) 有解的充要条件是 (\gcd(a, m) \mid b)。如果 (\gcd(a, m) \nmid b)那这个方程无解后面的操作全部免谈。为什么因为 (ax \equiv b \pmod{m}) 等价于存在整数 (y)使得[ ax - b my ]也就是[ ax - my b ]左边是 (a) 的倍数和 (m) 的倍数的线性组合它必然是 (\gcd(a, m)) 的倍数。所以 (b) 如果不是 (\gcd(a, m)) 的倍数方程就是无解的。如果满足条件解有多少个结论是在模 (m) 意义下恰好有 (d \gcd(a, m)) 个不同的解。这些解可以表示成[ x \equiv x_0 k \cdot \frac{m}{d} \pmod{m}, \quad k 0, 1, \dots, d-1 ]其中 (x_0) 是任意一个特解。举个例子感受一下。求解[ 6x \equiv 3 \pmod{9} ]先算 (\gcd(6, 9) 3)3 能整除 3所以有解且解的个数是 3 个。方程两边同时除以 3得到[ 2x \equiv 1 \pmod{3} ]在模 3 意义下 (2^{-1} \equiv 2)所以 (x \equiv 2 \pmod{3})。对应到模 9 意义下就是[ x \equiv 2, 5, 8 \pmod{9} ]验证一下(6 \times 2 12 \equiv 3 \pmod{9})(6 \times 5 30 \equiv 3 \pmod{9})(6 \times 8 48 \equiv 3 \pmod{9})。三个解全对。这两个结论有解条件和解的个数公式是解同余方程的总纲后续所有方法都是在回答同一个问题那个 (x_0) 怎么求出来。2. 手撕扩展欧几里得同余方程求解的核心数学2.1 从辗转相除法到顺带解方程既然 (ax \equiv b \pmod{m}) 等价于 (ax - my b)那问题就转化成了求不定方程 (ax my b) 的整数解。这里的关键工具是扩展欧几里得算法它的功能是给定整数 (a, b)求整数 (x, y)使得 (ax by \gcd(a, b))。普通欧几里得辗转相除大家都会它不断利用 (a b \times \lfloor a/b \rfloor (a \bmod b)) 这个关系缩小规模。核心是这样一个递推式[ \gcd(a, b) \gcd(b, a \bmod b) ]扩展欧几里得的思路是在这个递推过程中把每一层的系数也一并算出来。假设我们在递归的某一层已经得到了[ b x_1 (a \bmod b) y_1 \gcd(b, a \bmod b) ]由于 (a \bmod b a - \lfloor a/b \rfloor \cdot b)代入整理[ b x_1 (a - \lfloor a/b \rfloor \cdot b) y_1 a \cdot y_1 b \cdot (x_1 - \lfloor a/b \rfloor \cdot y_1) ]所以这一层的解就是[ x y_1, \quad y x_1 - \lfloor a/b \rfloor \cdot y_1这就是扩展欧几里得的核心递推。最底层的终止条件是 \(b 0\) 时\(\gcd(a, 0) a\)显然取 \(x 1, y 0\) 即可。 ### 2.2 边界条件与代码实现 代码逻辑上比很多人想象的要短 cpp int exgcd(int a, int b, long long x, long long y) { if (b 0) { x 1; y 0; return a; } long long x1, y1; int g exgcd(b, a % b, x1, y1); x y1; y x1 - (a / b) * y1; return g; }这里我特意把中间变量拆出来而不是用网上的交换传参写法。虽然交换传参更短但初学者特别容易被引用传递绕晕。拆出来写法虽然多了两行每一步在做什么一目了然。特别提醒一点中间乘积 ((a/b) * y1) 可能很大所以 (x, y, x1, y1) 建议都用long long。我见过很多选手在这里用int然后在系数比较大的时候直接溢出排查半天也找不到原因。2.3 用 exgcd 解同余方程的完整步骤有了exgcd解 (ax \equiv b \pmod{m}) 就按下面四步走计算 (d \gcd(a, m))。判断 (d) 是否整除 (b)不整除直接判定无解。用exgcd(a, m, x, y)得到 (ax my d) 的一组解 (x, y)。两边同时乘以 (b/d)得到原方程的一个特解 (x_0 x \cdot (b/d) \bmod m)。写成完整函数是这样的// 返回最小非负特解无解返回 -1 long long solve_linear_congruence(long long a, long long b, long long m) { long long x, y; long long d exgcd(a, m, x, y); if (b % d ! 0) return -1; long long x0 x * (b / d) % m; if (x0 0) x0 m; return x0; }注意为什么最后要乘 (b/d) 而不是直接乘 (b)因为exgcd求出的等式右边是 (d)不是 1。只有当 (d 1) 时exgcd求出的 (x) 才恰好是逆元。拿到特解后再利用前面说的通解公式就能列出所有解若 (d 1)模 (m) 意义下唯一解。若 (d 1)有 (d) 个不同的解间隔为 (m/d)。这一套流程熟练之后三十秒内可以手算完考场上是标准的保底题。3. 分数模运算模意义下的除法到底怎么算3.1 为什么需要逆元模世界里没有真正的除法先问一个看似简单的问题[ \frac{1}{2} \bmod 7 ? ]普通数学里(1/2 0.5)然后 (0.5 \bmod 7) 是什么没法定义。模运算只作用于整数所以我们必须换一种理解方式。思维转变的关键是把除法看成一个等式而不是一个算式。[ x \equiv \frac{a}{b} \pmod{m} ]它真正的意思是[ b x \equiv a \pmod{m} ]也就是说所谓(a/b) 模 (m)就是解方程 (bx \equiv a \pmod{m})。如果 (b) 和 (m) 互质这个方程有唯一解这个唯一解就记作 (a \cdot b^{-1} \bmod m)其中 (b^{-1}) 称为 (b) 模 (m) 的逆元。用生活例子打比方在 12 小时制的钟表上如果你想除以 7实际上是找一个数 (t)使 (7t \equiv 1 \pmod{12})。因为 (7 \times 7 49 \equiv 1 \pmod{12})所以在钟表世界里(1/7 7)。这在普通数学里荒谬在模算术世界里却完全成立。逆元存在的条件必须牢记(a) 模 (m) 存在逆元当且仅当 (\gcd(a, m) 1)。如果 (\gcd(a, m) 1)逆元不存在这时候求分数模就要非常小心通常题目会保证互素否则就需要用别的手段比如先化简。3.2 逆元的三种求法从通用到高效方法一扩展欧几里得求逆元求 (a^{-1} \bmod m)就是解[ a x \equiv 1 \pmod{m} ]即求 (ax my 1) 的解。代码long long mod_inverse(long long a, long long m) { long long x, y; long long d exgcd(a, m, x, y); if (d ! 1) return -1; // 不存在逆元 return (x % m m) % m; }这个方法对 (m)是否素数没有要求只要互质就能用。适用范围最广。方法二费马小定理求逆元模数为素数时的快速解法当 (m) 是素数时费马小定理给出[ a^{m-1} \equiv 1 \pmod{m} ]两边同时除以 (a)此处是乘逆元[ a^{-1} \equiv a^{m-2} \pmod{m} ]于是一行快速幂就完事了long long quick_pow(long long base, long long exp, long long mod) { long long res 1; base % mod; while (exp 0) { if (exp 1) res res * base % mod; base base * base % mod; exp 1; } return res; } // 模 p 为素数 long long mod_inverse_fermat(long long a, long long p) { return quick_pow(a, p - 2, p); }这个方法在组合数取模里最常用因为组合数问题通常给一个较大的素数模数比如 998244353、1000000007。方法三线性递推预处理逆元如果题目需要一次性算 (1) 到 (n) 的所有逆元逐个exgcd是 (O(n \log m))单个高频过程中可以被卡。更优的写法是 (O(n)) 递推核心公式是[ inv[i] (m - m/i) \cdot inv[m \bmod i] \bmod m ]推导不复杂设 (m qi r)其中 (q \lfloor m/i \rfloor)(r m \bmod i)。在模 (m) 意义下有 (qi r \equiv 0)两边同时乘以 (i^{-1} r^{-1})[ q r^{-1} i^{-1} \equiv 0 ]所以 (i^{-1} \equiv -q \cdot r^{-1} -(m/i) \cdot inv[m \bmod i])取正数就得到上面的公式。代码vectorlong long inv(n 1); inv[1] 1; for (int i 2; i n; i) { inv[i] (m - m / i) * inv[m % i] % m; }注意使用前提是 (m) 为素数且 (m n)否则别乱用。3.3 分数模运算与同余方程的互相转化说穿了分数模运算和同余方程就是一枚硬币的两面写法等价同余方程求解方式(a/b \bmod m)(b x \equiv a \pmod{m})先求 (b^{-1})再乘 (a)((n!)^{-1} \bmod m)(n! \cdot x \equiv 1 \pmod{m})exgcd 或费马小定理(\frac{n!}{k!(n-k)!} \bmod m)(k!(n-k)! \cdot x \equiv n! \pmod{m})分别求逆元后相乘这个转化思维非常重要。很多题面上是分数取模实际考的就是你能否把它翻译成同余方程。4. 同余方程组手写中国剩余定理的完整流程4.1 从单方程到方程组竞赛中同余方程很少单独出更多是以下形式已知某个数 (x) 除以 (m_1, m_2, \dots, m_n) 的余数分别是 (a_1, a_2, \dots, a_n)求 (x)。写成方程组[ \begin{cases} x \equiv a_1 \pmod{m_1} \ x \equiv a_2 \pmod{m_2} \ \vdots \ x \equiv a_n \pmod{m_n} \end{cases} ]如果模数 (m_1, m_2, \dots, m_n)两两互质直接用中国剩余定理CRT。如果两两不互质得先做合并后面会说。4.2 构造解的核心思想中国剩余定理的精髓是构造法。设[ M m_1 m_2 \cdots m_n ]对每个 (i)定义[ M_i \frac{M}{m_i}, \quad t_i M_i^{-1} \bmod m_i ]那么方程组的一组解是[ x \sum_{i1}^{n} a_i M_i t_i \bmod M ]为什么成立对第 (j) 个方程验证当 (i \neq j) 时(M_i) 是 (m_j) 的倍数所以那一项对 (m_j) 取模为 0当 (i j) 时(M_j t_j \equiv 1 \pmod{m_j})保留 (a_j)。每一项都在该管的方程里恰好贡献出 (a_j)在其他方程里悄悄消失这就是构造法的美妙之处。4.3 代码实现long long crt(const vectorlong long a, const vectorlong long m) { long long M 1; for (auto mi : m) M * mi; long long ans 0; for (int i 0; i (int)a.size(); i) { long long Mi M / m[i]; long long inv mod_inverse(Mi, m[i]); // 两两互质保证有逆元 ans (ans a[i] * Mi % M * inv) % M; } return (ans % M M) % M; }这个模板已经能应付大部分使用场景。M和Mi相乘时注意可能溢出能开__int128的题目尽量开或者改用快速乘。4.4 模数不互质时的合并策略如果模数不互质CRT 不能直接套。常见的做法是两两合并核心思想是假设有两个方程 (x \equiv a_1 \pmod{m_1}) 和 (x \equiv a_2 \pmod{m_2})。第一个方程给出 (x a_1 m_1 t)代入第二个方程[ a_1 m_1 t \equiv a_2 \pmod{m_2} ]即[ m_1 t \equiv a_2 - a_1 \pmod{m_2} ]这是一个标准线性同余方程用 2.3 节的方法解出 (t)带回 (x a_1 m_1 t)就得到合并后的方程。合并后的模数是 (\operatorname{lcm}(m_1, m_2))。这样两两合并 n-1 次就能处理任意模数同余方程组。这个思路在近年 CSP-S 模拟题里出现频率不低建议写一遍当成板子背熟。5. 案例实践三道典型同余方程题目完整拆解5.1 案例一裸逆元求解题题目求整数 (x \in [1, 1000000])使得 (3x \equiv 1 \pmod{1000000007})。输出最小的正整数解。一眼看出这是求 3 的逆元。模数是素数两种方法都能做。这里用扩展欧几里得演示#include bits/stdc.h using namespace std; 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 x1, y1; long long g exgcd(b, a % b, x1, y1); x y1; y x1 - (a / b) * y1; return g; } int main() { long long m 1000000007; long long x, y; exgcd(3, m, x, y); // 3x m*y gcd(3, m) 1 long long ans (x % m m) % m; cout ans \n; // 333333336 return 0; }验证一下(3 \times 333333336 1000000008)(1000000008 \bmod 1000000007 1)完全正确。这个题本身没难度但它考察的是最基础的翻译能力看到数 (x) 乘 3 后模 (10^97) 等于 1能不能立刻映射到求逆元。这套反射弧建不起来后面组合数、概率题全都寸步难行。5.2 案例二带判断的线性同余方程题目解同余方程 (15x \equiv 35 \pmod{100})。这道题如果直接套费马小定理那就错了因为 100 根本不是素数而且 (\gcd(15, 100) 5 \neq 1)。正确流程#include bits/stdc.h using namespace std; // exgcd 略同前 bool solve_congruence(long long a, long long b, long long m, vectorlong long solutions) { long long x, y; long long d exgcd(a, m, x, y); if (b % d ! 0) return false; // 无解 long long x0 x * (b / d) % m; x0 (x0 % m m) % m; long long step m / d; for (long long k 0; k d; k) { solutions.push_back(x0 k * step); } return true; } int main() { vectorlong long sol; if (solve_congruence(15, 35, 100, sol)) { for (auto v : sol) cout v (v % 100) \n; } return 0; }先用exgcd(15, 100, x, y)会得到 (15x 100y 5) 的一组解比如 (x 7实际上 15×7 - 100×1 5所以 (x 7) 对应的特解是 (7 \times (35/5) 49)。模 100 下 49 确实是解(15 \times 49 735 \equiv 35 \pmod{100})。通解形式[ x \equiv 49 20k \pmod{100}, \quad k 0, 1, 2, 4 ]所以答案是 49、69、89、9按 k0,1,2,3 算分别是 49、69、89、109 取模得 9。很多新手拿到 49 就走了漏掉剩下 4 个解。这正好呼应 1.2 节解的数量结论——别只求一个解就交卷。5.3 案例三组合数取模中隐含的同余方程题目计算 (C(n, k) \bmod p)其中 (p 998244353) 是素数(n, k \le 10^6)。这是提高组最常见的大综合题。表面上是组合数本质上就是分数模运算 同余方程。拆解一下[ C(n, k) \frac{n!}{k!(n-k)!} \bmod p ]这个分数不能直接算需要转成[ n! \cdot (k!)^{-1} \cdot ((n-k)!)^{-1} \bmod p ]预处理好阶乘和逆元剩下的就是查表#include bits/stdc.h using namespace std; const int MOD 998244353; const int MAXN 1e6 5; long long fact[MAXN], invfact[MAXN]; long long quick_pow(long long base, long long exp) { long long res 1; while (exp 0) { if (exp 1) res res * base % MOD; base base * base % MOD; exp 1; } return res; } void pre_process(int n) { fact[0] 1; for (int i 1; i n; i) fact[i] fact[i - 1] * i % MOD; invfact[n] quick_pow(fact[n], MOD - 2); // 费马小定理求逆元 for (int i n; i 1; i--) invfact[i - 1] invfact[i] * i % MOD; } int main() { int n, k; cin n k; pre_process(n); long long ans fact[n] * invfact[k] % MOD * invfact[n - k] % MOD; cout ans \n; return 0; }这里为什么不用线性递推逆元因为我们要的是阶乘的逆元不是每个数的逆元。更优雅的做法是只求一个invfact[MAXN]然后倒推回来这样复杂度是 (O(n \log p))飞快。这道题把前面所有知识点串起来了线性同余方程求逆元、费马小定理快速求逆、分数模运算除法转乘逆元。刷到这里你会发现所谓数论基础生题其实都是这十几个板子的组合拳。6. 实战易错点与调试经验6.1 负数取模C 的坑你要先补上C 的%运算符和数学意义上的模运算有个致命差异结果的符号跟随被除数。比如(-5) % 3在 C 里结果是-2但数学上 ( -5 \bmod 3 1)。所以任何时候算完模数都要用这一行把它归正long long norm(long long x, long long mod) { return (x % mod mod) % mod; }注意先对x % mod取一次再加mod最后再取一次否则x -10^18时可能出问题。这个norm函数几乎是所有同余类算法的地基忘记用一次就可能把后面全部带偏。6.2 乘法溢出long long 不是万能的mod_inverse函数里x * (b / d) % m这里x可能接近 (10^9)(b/d) 也可能接近 (10^9)一乘就是 (10^{18})还在long long范围内但很极限。如果模数再大点比如到 (10^{12})就需要用快速乘法long long mul_mod(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; }或者干脆遇到大模数直接用__int128不同的编译器都支持简单粗暴。6.3 无解判定别偷懒线性同余方程solve_linear_congruence里一定要先把gcd算出来判断整除不能直接求逆元。exgcd返回的d 1只是逆元存在的情况但实际上方程 (ax \equiv b \pmod m) 在 (\gcd(a,m) \mid b) 时一定有解哪怕不互质也有。这个区别是送分题和送命题的分水岭。6.4 写板子时最实用的调试套路我的习惯是每个数论板子写完先跑一遍暴力对拍。比如求逆元直接暴力验证a * inv(a) % m 1。解同余方程暴力枚举x从 0 到 m-1检查哪些满足方程然后看程序输出和暴力结果是否一致。模数小的情况下这个验证几毫秒就完成费不了多少时间但能帮你把公式抄错负号写反这类低级失误当场揪出来。还有一个经验所有返回最小非负解的函数最后统一norm一下。这个规范性动作看起来是多余实际上能省掉无数个因为边界负数产生的神秘 bug。我现在写任何模运算板子第一条规则就是所有输出必须落在 ([0, m)) 区间内。6.5 把板子整理成自己的模板库学到这个阶段我强烈建议你整理一份自己的数论模板至少包含以下函数exgcd(a, b, x, y)扩展欧几里得mod_inverse(a, m)通用逆元quick_pow(a, exp, mod)快速幂solve_linear_congruence(a, b, m)线性同余方程求解crt(a[], m[])中国剩余定理互质版pre_inv(n, p)线性逆元预处理pre_fact(n, p)阶乘与阶乘逆元预处理每个函数都配上注释和一句前提条件。考试时不是为了现场推公式而是为了把宝贵的十几分钟从公式推导里省出来留给真正的核心算法。我自己教学生的经验是同余方程这个专题最难的不是某个算法记不住而是意识不到位——看到题压根没想到要转成同余方程。所以平常做题别只看答案要刻意培养翻译习惯题目里出现除以余数同余这些字眼立刻在草稿纸上写 (ax \equiv b \pmod{m}) 的标准形。练多了你会发现很多所谓难题的题眼就是一个你闭着眼睛都能解的线性同余方程。信竞这条路没有捷径但你可以把每一个基础专题都吃得很透让考场上每一道基础题都变成送分题。同余方程这一块做到这种程度就及格了再配合逆元和 CRT数论部分的大头已经拿下了。剩下的就是多刷题把速度提上来。