企业官网建设流程全解析

1. 为什么刷题老是遇到"取模题"：同余方程在算法题中的真正位置

如果你刷算法题超过一个月，一定会发现一个现象：题目里动不动就出现"对 10^9+7 取模"、"结果可能很大，请对 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 同余方程两条最核心的转化链：模意义下的加减乘除

为什么很多人觉得同余方程难？因为他们在实数域待习惯了，总想着"移项、通分、消元"，到了模的世界里这些操作全部要重新学。同余方程最核心的三条性质，其实都是直觉：

1. 加法与乘法可交换：a + c ≡ b + c (mod m)，a * c ≡ b * c (mod m)。这跟普通等式几乎一样，直接放心用。
2. 除法不能随便做：a ≡ b (mod m)不能直接推出a / c ≡ b / c (mod m)，除非 c 和模数 m 互质。这是新手最容易踩的坑。
3. 指数可以降幂：如果 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) = 2，2 不能整除 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^9+7、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。典型的表象有：

1. "一个物品的数量，每 3 个一数余 2，每 5 个一数余 3，每 7 个一数余 2，求最小值"——这是直接铺开讲。
2. "给定 n 组a_i, m_i，求最小的非负整数 x"——这是模板题的外壳。
3. "递推式里出现了多种不同模数的周期约束"——这种稍微隐晦一点，需要你自己把条件翻译成同余式。

经典 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 vector<long long> &a, const vector<long 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 = 6，m2 = 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) pair<long 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。这时候有几个策略：

1. 如果题目允许，用__int128中间量过渡，C++ 的 GCC 系编译器支持，竞赛很常用。
2. 如果模数数量少，可以用快速乘（类似快速幂，把乘法拆成加法）逐项累加，避免整段溢出。
3. 有些题目的 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 次剩余。

这两种问题直接硬解都是死路，因为它们背后没有一个像"一元一次方程"那样简单的通法。但竞赛和面试里常用的套路是BSGS（Baby-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 变化。于是你分两步走：

1. 小步（Baby Step）：把所有j对应的b * a^j存进哈希表，键是它的值，值是最小的 j。这一步时间复杂度O(sqrt(m))。
2. 大步（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_map<long 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 次剩余问题转化成离散对数问题。整体思路分三步：

1. 找到一个原根 g，使得 g 的幂次能生成模 p 下的所有非零剩余（如果找不到，可以用第二个原根，或者题目直接给）。
2. 把 x 表示成x = g^t，同时把 b 表示成b = g^s。这里的 s 就是"b 的离散对数"，用 BSGS 求。
3. 原方程变成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) { vector<long 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_map<long 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 识别套路：同余题目常见的六类外壳

我总结下来，同余方程题基本披着这六种外衣：

你在读题的时候，第一步永远是提取模数是谁、未知量是谁、已知量是谁。不是所有"取模"题都需要同余方程，但如果未知量出现在指数、系数或方程右侧，那就大概率是同余问题。

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 的约分经常被漏掉。有次我写代码忘了把模数也约掉，直接拿原模数去取模，结果正确解是x0=3，我输出x0=8，全错。约分必须三处一起约：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 循环 j=0..len-1，存 (b * a^j, j) 进哈希表 step4: 预处理 a^len step5: Giant Step 循环 i=1..len，查 (a^(i*len)) step6: 查到即得 x = i*len - j，没查到返回无解

BSGS 的退化情况很多，最容易被坑的是b = 1。此时 x = 0 是平凡解，但 BSGS 的 Baby Step 循环在 j = 0 时存了b * a^0 = 1，Giant 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-l+1)) % MOD

如果你忘了取模就直接减，会得到负数；如果你选了一个太小的 MOD，冲突概率急剧上升。这里同余方程提供的核心洞察是：哈希冲突的本质是两个不同的串恰好模 MOD 同余。你没法完全避免冲突，只能降低概率。

工程上的常见降冲突手段：

• 选一个大质数做模数，比如1e9+7、1e9+9、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

你看起来这公式简单，但参数选不对，随机序列会非常短甚至直接卡死。比如m=10，a=2，c=0，初始值 1，序列就是1,2,4,8,6,2——循环只有 4 个不同的数，而且 2 和 6 之间反复横跳，这哪是随机，分明是摆烂。

工程标准里常用的一组参数是a=1103515245, c=12345, m=2^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 合并，默写三五次之后你会发现那几个低级错误——负数没转正、约分没约模数、循环边界差一——基本都绝迹了。同余方程这块知识，真正的分水岭不在"会不会背模板"，而在"能不能看出题目在考同余"。而这，只能靠多做题攒感觉。