企业官网建设流程全解析

每年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})，(x=1) 和 (x=3) 都满足，因为 (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}) 就按下面四步走：

1. 计算 (d = \gcd(a, m))。
2. 判断 (d) 是否整除 (b)，不整除直接判定无解。
3. 用exgcd(a, m, x, y)得到 (ax + my = d) 的一组解 (x, y)。
4. 两边同时乘以 (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])，取正数就得到上面的公式。代码：

vector<long 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 分数模运算与同余方程的互相转化

说穿了，"分数模运算"和"同余方程"就是一枚硬币的两面：

这个转化思维非常重要。很多题面上是"分数取模"，实际考的就是你能否把它翻译成同余方程。

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_{i=1}^{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 vector<long long>& a, const vector<long 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^9+7) 等于 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, vector<long 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() { vector<long 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（按 k=0,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，数论部分的大头已经拿下了。剩下的，就是多刷题把速度提上来。