1. 为什么刷题老是遇到取模题同余方程在算法题中的真正位置如果你刷算法题超过一个月一定会发现一个现象题目里动不动就出现对 10^97 取模、结果可能很大请对 k 取模、给定模数 m求满足同余关系的最小正整数。很多新手看到取模两个字就头疼觉得这是数学题不是算法题甚至想绕开走。但说实话同余方程在算法题里的地位比你会做的二分查找和动态规划还要基础——它是大量题目的地基。1.1 同余不是数学课的概念而是算法题的通用语言先看一个所有入门者都经历过的问题为什么斐波那契数列要取模直接递推不就行了你算到第 50 项就发现long long都快兜不住了题目要求输出f(n) % m就是为了让答案落在可控范围内。但光知道取模防溢出只是第一层第二层才是关键取模之后加减乘都依然成立。同余方程的定义其实就是这两句话如果(a - b)能被m整除就记作a ≡ b (mod m)读作a 与 b 关于模 m 同余。同余方程长这样a * x ≡ b (mod m)。你要做的事是在模 m 的体系下把 x 解出来而不是在实数域里解方程。为什么它重要因为算法题里很多时候我们根本不关心真实值是多少只关心模 m 之后的值。比如组合数 C(n, k) 的真实值可能是一个天文数字但题目只要求模998244353后的结果比如 RSA 解密过程本质就是在解一个同余方程又比如一个递推公式f(n) (f(n-1) f(n-2)) % m这整个递推过程都是在模 m 的封闭世界里进行的——你不需要跨出这个边界去做任何除法或比较大小。所以我的第一个建议是把所有取模题都当成同余方程题来看。取模只是表象同余才是本质。1.2 同余方程两条最核心的转化链模意义下的加减乘除为什么很多人觉得同余方程难因为他们在实数域待习惯了总想着移项、通分、消元到了模的世界里这些操作全部要重新学。同余方程最核心的三条性质其实都是直觉加法与乘法可交换a c ≡ b c (mod m)a * c ≡ b * c (mod m)。这跟普通等式几乎一样直接放心用。除法不能随便做a ≡ b (mod m)不能直接推出a / c ≡ b / c (mod m)除非 c 和模数 m 互质。这是新手最容易踩的坑。指数可以降幂如果 a 和 m 互质根据欧拉定理a^φ(m) ≡ 1 (mod m)所以一个大到爆的指数可以按φ(m)取模后计算。这个性质在求超大指数模的题目里是核心杀招。在实际做题时你可以记住两条转化链链一分数转乘法逆元遇到x / a这种除法在模 m 的世界里不能直接除要改成x * inv(a)其中inv(a)是 a 在模 m 下的逆元满足a * inv(a) ≡ 1 (mod m)。链二同余转整除x ≡ a (mod m)等价于存在整数 k 使得x a k * m。这个转化在求解满足多个同余条件的最小整数时极其常用后面讲中国剩余定理时要反复用它。这两条链就像工具箱里的扳手和螺丝刀几乎所有同余方程题目最后都会落到这两个操作上。2. 线性同余方程的完整解法链从逆元到扩展欧几里得线性同余方程是同余方程里的一元一次方程形式是最简单的a * x ≡ b (mod m)。可别小看它后面所有高阶玩法——中国剩余定理、离散对数、组合数取模全都要用到这一层的解法。这里我直接把完整解法链拆开讲。2.1 判断有没有解简单到看一眼的 gcd 判据在实数方程里ax b只要a ! 0就有唯一解。但同余方程不一样它可能无解也可能有很多解。判定条件非常简单当且仅当gcd(a, m)能整除 b 时方程a * x ≡ b (mod m)有解。举个例子2 * x ≡ 3 (mod 6)gcd(2, 6) 22 不能整除 3所以无解。为什么因为你把2x写成2x ≡ 3 (mod 6)左边永远是偶数模 6 之后只可能是 0、2、4绝对不可能变成 3。所以看到方程先算 gcd这就是最快的判据。如果gcd(a, m) g且g | b那么方程有g个不同的解在模 m 意义下。怎么理解你可以先把方程左右两边同时约掉 g变成(a/g) * x ≡ (b/g) (mod (m/g))约分之后gcd(a/g, m/g) 1此时方程在模m/g下有唯一解但回到模 m 下这个解还可以平移 g 个位置。实际做题的时候我建议直接解约分后的方程最后如果有需要再把所有解都写出来。2.2 扩展欧几里得为什么能顺便求逆元含推导面试里经常考求 x 的模逆元很多人会背一行代码但问为什么就是一脸懵。我先给结论求a * x ≡ 1 (mod m)的逆元本质上是在解a * x m * y 1这就是扩展欧几里得干的事。你可能会问为什么同余方程a * x ≡ b (mod m)可以改写成一个普通等式因为同余的定义就是a*x - b是 m 的倍数也就是说存在整数 y 使得a*x - b m * (-y)移项就是a*x m*y b。这下你看到了——它就是一个普通的二元一次不定方程x 和 y 都是整数。扩展欧几里得算法就是用来求a*x m*y gcd(a, m)的一组整数解的。推导过程其实不复杂。欧几里得的递归思想是gcd(a, m) gcd(m, a % m)。假设我们已经求出了下面这组解m * x1 (a % m) * y1 gcd(m, a % m)把a % m a - (a/m) * m代进去整理一下m * x1 (a - (a/m) * m) * y1 (x1 - (a/m) * y1) * m y1 * a gcd(a, m)所以新的解就是x y1 y x1 - (a/m) * y1递归出口是m 0时gcd(a, 0) a显然取x 1, y 0。把这个思路写成代码就是经典的exgcd。当你要求a在模m下的逆元时只要gcd(a, m) 1直接跑exgcd(a, m)得到的 x 就是逆元。但注意x 可能是负数C 里取模会得到负值一定要用(x % m m) % m转成最小正整数解。// 扩展欧几里得求解 a*x m*y gcd(a, m)返回 gcd 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 g exgcd(b, a % b, x, y); long long t x; x y; y t - (a / b) * y; return g; } // 求 a 在模 m 下的逆元前提 gcd(a, m)1 long long mod_inverse(long long a, long long m) { long long x, y; long long g exgcd(a, m, x, y); if (g ! 1) { // 逆元不存在 return -1; } return (x % m m) % m; }2.3 模数是质数与模数是合数的不同处理习惯做题多了你会形成一个条件反射题目给你10^97、998244353这种质数模数和给你一个2024这种合数模数解法是完全不同的。为什么如果模数是质数 p而且 a 不是 p 的倍数那么a^(p-2) mod p就是 a 的逆元。这就是费马小定理的直接应用a^(p-1) ≡ 1 (mod p)两边同乘a^(-1)得a^(p-2) ≡ a^(-1) (mod p)。用快速幂求一行代码的事比扩展欧几里得好写多了。如果模数是合数费马小定理不一定成立只能用扩展欧几里得而且前提还是gcd(a, m) 1。一旦不互质逆元压根不存在题目就会换一种考法——比如让你约分明再求。还有一个我踩过多次的坑费马小定理的指数必须是(p-2)而不是别的数。有人记成a^(p-1)也返回了 1拿去当逆元用结果答案天差地别。切记a^(p-2)才是乘法逆元a^(p-1)只是验证同余关系用的。如果你的题目里模数 p 很大注意用快速幂时每一步都取模防止乘法溢出在 C 里建议用__int128或者在乘法函数里按位拆分。快速幂求逆元模板 a^(p-2) mod p如果 p 是质数且 a 不是 p 的倍数3. 中国剩余定理多个方程联立时的高效合并方案如果说线性同余方程是单个条件求解那中国剩余定理以下简称 CRT就是多个条件联立求解。它解决的问题长这样x ≡ a1 (mod m1) x ≡ a2 (mod m2) ... x ≡ ak (mod mk)题目通常会说这个数除以 3 余 2除以 5 余 3除以 7 余 2求这个数最小是多少——这就是经典的同余方程组直接套 CRT 就能秒。3.1 什么场景下题目应该用 CRT我先说结论只要看到题目同时给出多个模数且要求找同时满足所有模条件的数十有八九是 CRT。典型的表象有一个物品的数量每 3 个一数余 2每 5 个一数余 3每 7 个一数余 2求最小值——这是直接铺开讲。给定 n 组a_i, m_i求最小的非负整数 x——这是模板题的外壳。递推式里出现了多种不同模数的周期约束——这种稍微隐晦一点需要你自己把条件翻译成同余式。经典 CRT 有个严格前提所有模数两两互质。在这个前提下解法非常优雅。设M m1 * m2 * ... * mk对每个方程单独构造一个解再叠加起来对第 i 个方程构造Mi M / mi。因为所有模数两两互质所以gcd(Mi, mi) 1于是 Mi 在模 mi 下有逆元inv_i。构造ci Mi * inv_i它满足当j ! i时ci ≡ 0 (mod mj)因为 ci 是 Mj 的倍数当j i时ci ≡ 1 (mod mi)。最后答案x Σ (ai * ci) mod M。我强烈建议你亲手推一遍这个构造过程因为每个 ci 只在第 i 个方程里贡献 1、在其他方程里贡献 0这个思想在后续很多数论题里都会反复出现。// 传统 CRT模数两两互质 long long crt(const vectorlong long a, const vectorlong long m) { long long M 1; for (long long v : m) M * v; 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) % M; } return ans; }3.2 模数不互质怎么救增量合并法现实是残酷的——很多题目不给你两两互质这个舒适区。比如m1 6m2 10它们公约数是 2传统 CRT 直接失效。那怎么办这里我讲一种更通用也更耐用的方法增量合并法。你别管它叫扩展中国剩余定理理解成每两个方程逐个合并就行。核心思路是把两个方程合并成一个方程。假设我们现在有两个方程x ≡ a1 (mod m1) x ≡ a2 (mod m2)把第一个方程写成x a1 m1 * t代入第二个方程a1 m1 * t ≡ a2 (mod m2) m1 * t ≡ a2 - a1 (mod m2)这就是一个标准的线性同余方程直接解 t。有解得先决条件是gcd(m1, m2)能整除(a2 - a1)否则整个方程组无解。一旦解出 t 的一个特解 t0那么 x 的通解就是x a1 m1 * (t0 k * (m2 / g)) (a1 m1 * t0) k * lcm(m1, m2)也就是说两个方程合并成了一个新的同余方程x ≡ a1 m1 * t0 (mod lcm(m1, m2))其中lcm(m1, m2) m1 / g * m2。把这个新方程跟下一个方程再合并重复 n-1 次就完事了。// 合并两个同余方程返回 {a, m} 表示 x ≡ a (mod m) pairlong long, long long merge_crt(long long a1, long long m1, long long a2, long long m2) { long long x, y; long long g exgcd(m1, m2, x, y); long long diff a2 - a1; // 检查是否有解gcd(m1,m2) 必须整除 diff if (diff % g ! 0) return {-1, -1}; // x 是 m1*x ≡ g (mod m2) 的特解需要放大到 diff/g x (x % (m2 / g) (m2 / g)) % (m2 / g); x x * (diff / g) % (m2 / g); long long new_m m1 / g * m2; long long new_a (a1 m1 * x) % new_m; if (new_a 0) new_a new_m; return {new_a, new_m}; }这里有两个很容易错的地方我都吃过亏先约分再取模求逆元的时候我一开始直接拿 m2 当模数但约掉 g 之后模数应该是m2 / g。不然即使有解求出来的 t 周期也不对。求 x 的放大倍数exgcd给的是m1*x ≡ g (mod m2)的特解而你现在需要的是m1 * t ≡ diff (mod m2)所以 x 要乘diff / g并且要对m2 / g取模。3.3 实战提醒CRT 与数据范围的配合long long 溢出CRT 里最阴间的不是数学而是乘法溢出。你算M m1 * m2 * ... * mk如果每个 mi 都是10^9级别k 稍微大一点M 直接爆long long。这时候有几个策略如果题目允许用__int128中间量过渡C 的 GCC 系编译器支持竞赛很常用。如果模数数量少可以用快速乘类似快速幂把乘法拆成加法逐项累加避免整段溢出。有些题目的 M 虽然超大但最终答案范围很小可以用边算边取模而不是真的算完整 M——但这要求你把公式理解透知道哪些地方必须用模 M而哪些地方可以用模局部值。我有一个实战习惯写 CRT 前先估算所有 mi 的乘积量级。如果乘起来超过1e18直接用快速乘或者__int128不要在 double 里比较——浮点数在巨大整数面前是不可信的我经历过一次精度丢失排查了半小时才发现是double比较惹的祸。4. 高次同余方程实战BSGS、n 次剩余与哈希加速线性同余方程是一次的但刷题碰到幂次的时候你就要换武器了。这里有两种典型问题问题一知道底数和结果求指数即a^x ≡ b (mod m)里的 x。这叫离散对数。问题二知道指数和结果求底数即x^k ≡ b (mod m)里的 x。这叫 n 次剩余。这两种问题直接硬解都是死路因为它们背后没有一个像一元一次方程那样简单的通法。但竞赛和面试里常用的套路是BSGSBaby-Step Giant-Step大步小步法它专门解决离散对数问题而且思路极其巧妙。4.1 BSGS 解决离散对数问题的本质大步小步的变址查表先约定a^x ≡ b (mod m)且gcd(a, m) 1。BSGS 的核心是用空间换时间。设一个步长参数len ceil(sqrt(m))把指数 x 写成x i * len - j其中 i 的范围是[1, len]j 的范围是[0, len-1]。为什么要这么拆因为这样做之后原方程变成a^(i*len - j) ≡ b (mod m) a^(i*len) ≡ b * a^j (mod m)左边的值只随 i 变化右边的值只随 j 变化。于是你分两步走小步Baby Step把所有j对应的b * a^j存进哈希表键是它的值值是最小的 j。这一步时间复杂度O(sqrt(m))。大步Giant Step从 i 1 开始逐个计算a^(i*len)去哈希表里查有没有相等的值。一查到x i * len - j就是答案。本质上BSGS 就是把遍历所有可能的 x这个 O(m) 的活硬生生拆成了两个 O(sqrt(m)) 的活再用哈希表把两个队伍串联起来。类似查字典你先翻索引建立词条再查词条拿到页码比从头到尾翻书快了一个量级。// BSGS 求 a^x ≡ b (mod m) 的最小非负整数 x要求 gcd(a, m) 1 long long bsgs(long long a, long long b, long long m) { unordered_maplong long, long long hash; long long len (long long)sqrt(m) 1; long long cur 1; // Baby Step存储 b * a^j for (long long j 0; j len; j) { if (!hash.count(cur)) hash[cur] j; cur cur * a % m; } // 计算 a^len 和其逆元也可以预处理 long long step 1; for (long long i 0; i len; i) step step * a % m; cur 1; // Giant Step查表 for (long long i 1; i len; i) { cur cur * step % m; // 目前是 a^(i*len) if (hash.count(cur)) { long long ans i * len - hash[cur]; if (ans 0) return ans; } } return -1; }注意这里我用unordered_map它平均 O(1) 查询。如果你用map复杂度是 O(log n)在模数是1e9以上时差距并不致命但写成unordered_map更贴近竞技标准化。一个小细节Baby Step 存储的时候同一个值可能出现多次要存最小的 j否则求出来的 x 可能不是最小的甚至可能算错。我是吃过这个亏的——有个周期性的值被大的 j 覆盖了结果答案大了一轮。4.2 n 次剩余的转化变成一次方程再解如果题目让你解x^k ≡ b (mod m)而模数是质数 p先别慌。这种问题的常规解法是利用原根把 n 次剩余问题转化成离散对数问题。整体思路分三步找到一个原根 g使得 g 的幂次能生成模 p 下的所有非零剩余如果找不到可以用第二个原根或者题目直接给。把 x 表示成x g^t同时把 b 表示成b g^s。这里的 s 就是b 的离散对数用 BSGS 求。原方程变成g^(k*t) ≡ g^s (mod p)即k * t ≡ s (mod (p-1))——这又回到了第二章节的线性同余方程。看到没有高次问题转一圈又落到了线性同余方程上。这也是为什么我前面花了大篇幅讲线性同余方程它是所有同余问题的最小公因数。很多选手写到这里会卡在怎么找一个模 p 的原根。这里我分享一个简单好记的找法对p-1做质因数分解然后从小到大试 g如果对 p-1 的每个质因子 q都有g^((p-1)/q) ! 1 (mod p)那 g 就是原根。因为模 p 下 g 的阶只有等于 p-1 才叫原根而阶整除 p-1逐个排除小于 p-1 的因子即可。// 找模 p 的原根 long long primitive_root(long long p) { vectorlong long factors; long long phi p - 1, tmp phi; for (long long i 2; i * i tmp; i) { if (tmp % i 0) { factors.push_back(i); while (tmp % i 0) tmp / i; } } if (tmp 1) factors.push_back(tmp); for (long long g 2; ; g) { bool ok true; for (long long q : factors) { if (qpow(g, phi / q, p) 1) { ok false; break; } } if (ok) return g; } }4.3 哈希表与 unordered_map 的选型建议BSGS 的时间瓶颈很大程度取决于哈希表。我个人的建议是模数 m 不大小于1e7时直接用数组做哈希即开一个够大的数组把值当下标查询是真正的 O(1)常数极小。这比unordered_map快很多。模数大时用unordered_maplong long, long long但要注意它的常数因子。如果你开了 O2 优化还超时可以考虑手写一个简单的链表式哈希桶专门存long long对long long的映射会比 STL 快 20%-30%。千万不要在unordered_map里存pair做键会引入无谓的哈希开销。直接用值当下标或者值对 value 做哈希。此外还有一个经典优化Baby Step 的步长可以预先算好 a^j 的时候用滚动乘法而不是每次都快速幂。如上代码所示cur cur * a % m就完事了一次乘法 O(1)而qpow每次 O(log m)差距立竿见影。5. 从题目识别到模板落地三套可直接抄的解题骨架讲了这么多理论最后总得落到拿到一道题怎么下手。我不会让你把所有知识零散地拼起来而是直接给你三套解题骨架。这三套骨架覆盖了大多数同余方程题目你在实战中按图索骥就行。5.1 识别套路同余题目常见的六类外壳我总结下来同余方程题基本披着这六种外衣题目外壳典型特征对应武器纯线性同余直接给a*x ≡ b (mod m)求最小正解或总解数扩展欧几里得 约分分数取模给形如(p/q) mod M的式子要求先求 q 的逆元再乘 p费马小定理M 为质数或扩展欧几里得同余方程组多个除以几余几的约束求最小非负整数CRT / 增量合并指数取模底数很大或指数非常大求模结果快速幂 欧拉定理降幂离散对数a^x ≡ b (mod m)求 xBSGS组合数取模计算 C(n, k) mod pn 和 k 巨大卢卡斯定理 逆元 快速幂你在读题的时候第一步永远是提取模数是谁、未知量是谁、已知量是谁。不是所有取模题都需要同余方程但如果未知量出现在指数、系数或方程右侧那就大概率是同余问题。5.2 骨架一线性同余方程通用主程序step1: 读入 a, b, m step2: g gcd(a, m) step3: 如果 b % g ! 0输出无解 step4: a a/g, b b/g, m m/g step5: 用 exgcd 求 a 在模 m 下的逆元 inv step6: x0 b * inv % m step7: 输出 x0并可按 x x0 k * m 列举所有解说一个动作step4 的约分经常被漏掉。有次我写代码忘了把模数也约掉直接拿原模数去取模结果正确解是x03我输出x08全错。约分必须三处一起约a、b、m。5.3 骨架二CRT 增量合并主程序step1: 初始化 pair {a1, m1} step2: 逐个读取 (a_i, m_i)调用 merge_crt(pair.first, pair.second, a_i, m_i) step3: 中间若返回 {-1, -1}直接判定无解 step4: 全合并完得到 x ≡ a_final (mod m_final) step5: 输出最小非负整数 x a_final % m_final注意负值转正这套骨架特别适合模数不互质的题目。如果你看到题目保证模数两两互质可以直接用经典 CRT 更简洁如果没保证别赌它直接用增量合并。增量合并也能处理互质情况只是多跑几轮 gcd 而已性能不会有问题。5.4 骨架三BSGS 离散对数主程序step1: 特判 a % m 0 的情况此时底数和模数不互质BSGS 失效 step2: len ceil(sqrt(m)) step3: Baby Step 循环 j0..len-1存 (b * a^j, j) 进哈希表 step4: 预处理 a^len step5: Giant Step 循环 i1..len查 (a^(i*len)) step6: 查到即得 x i*len - j没查到返回无解BSGS 的退化情况很多最容易被坑的是b 1。此时 x 0 是平凡解但 BSGS 的 Baby Step 循环在 j 0 时存了b * a^0 1Giant Step 在 i 0 时就查到了如果你的循环从 i 1 开始会错过 0 这个解。所以我自己写 BSGS 总是会加一句特判if (b 1) return 0;非常省事。另外如果题目要求最小正整数解而不是非负解也要单独处理别直接用 0 去凑。6. 同余方程在真实算法工程中的延伸哈希、随机数与校验很多人觉得同余方程只是比赛用的跟实际工程没关系。其实不然同余思想深深渗透在系统设计、数据结构和安全领域。这里我挑三个最常碰到的场景讲下同余思维是怎么在工程里变形的。6.1 字符串哈希本质是模哈希冲突的管理你写字符串哈希时一定见过这个经典写法把字符串看成一个 base 进制的大整数再对一个大质数取模h[i] (h[i-1] * base s[i]) % MOD这本质上就是在做同余计算。你计算的是字符串的模 MOD 值每次查询子串哈希就是做减法sub_hash (h[r] - h[l-1] * base^(r-l1)) % MOD如果你忘了取模就直接减会得到负数如果你选了一个太小的 MOD冲突概率急剧上升。这里同余方程提供的核心洞察是哈希冲突的本质是两个不同的串恰好模 MOD 同余。你没法完全避免冲突只能降低概率。工程上的常见降冲突手段选一个大质数做模数比如1e97、1e99、998244353。base 选一个大于字符集大小的奇数比如 131、13331避免字符间哈希值重叠。追求极致安全就做双哈希用两组不同的 base 和 MOD分别计算只有两组值都相等才算匹配。这就是把碰撞概率从1/MOD降到了1/(MOD1*MOD2)。这套东西背后的道理全是同余两个串S1和S2如果满足S1 ≡ S2 (mod MOD1)且S1 ≡ S2 (mod MOD2)那么它们模lcm(MOD1, MOD2)也同余而lcm近似两者的乘积。所以说到底双哈希就是 CRT 思想的一次工程应用。6.2 随机算法里的同余陷阱伪随机数生成器PRNG里最著名的一族叫线性同余生成器形式是next (a * prev c) mod m你看起来这公式简单但参数选不对随机序列会非常短甚至直接卡死。比如m10a2c0初始值 1序列就是1,2,4,8,6,2——循环只有 4 个不同的数而且 2 和 6 之间反复横跳这哪是随机分明是摆烂。工程标准里常用的一组参数是a1103515245, c12345, m2^31这组参数能让序列周期达到m。但如果你直接把a和c换掉周期可能会缩短几个数量级。这里的教训是伪随机序列周期的上限是模数 m想要满周期就必须满足几条同余条件c 和 m 互质a-1 被 m 的所有质因子整除等等。这些条件不是说背下来就完了你得理解它们本质是在保证递推函数是一个满射而满射性的证明恰好会用到同余转移矩阵的行列式判断。6.3 同余与校验算法的关系最后聊一个冷门但实用的方向校验算法。像**循环冗余校验CRC**这种经典校验本质上是在模 2 的多项式环里做同余除法数据被当成一个多项式生成多项式作为模数校验码就是数据多项式对生成多项式取模的余数。这和整数同余是同一个数学结构只不过把整数换成了系数为 0/1 的多项式。我最初学 CRC 的时候怎么都想不通为什么 CRC 能查错、但查不出所有错。后来用同余的视角一看就明白了任何错误 e 如果恰好能被生成多项式整除也就是e ≡ 0 (mod G)那校验码就不会变错误就被漏掉了。所以校验能力本质上取决于生成多项式能覆盖多少种典型错误模式——这和模数选得好不好决定哈希冲突概率是同一个道理。从工程降级回算法题视角你会发现在竞赛里经常碰到的字符串最小表示法、循环节检测、约瑟夫环模拟等题目底子里都有模周期和同余的影子。你练同余方程练的不只是几个板子而是一种**把无限变成有限、把连续变成离散**的思维。这种思维在算法工程师的日常里比如设计分布式 ID、做分库分表的取模路由、写限流滑窗时都会反复用到。最后分享一个小技巧我刷同余题目的时候习惯把每个板子都默写一遍而不是复制粘贴。特别是 exgcd 和 CRT 合并默写三五次之后你会发现那几个低级错误——负数没转正、约分没约模数、循环边界差一——基本都绝迹了。同余方程这块知识真正的分水岭不在会不会背模板而在能不能看出题目在考同余。而这只能靠多做题攒感觉。