模运算下没有现成的除法——扩展欧几里得算法能求出"模意义下的倒数"，把除法问题转换成乘法问题。
1 模块讲过的欧几里得算法（辗转相除法）能求出 gcd(a,b)，但只告诉我们"最大公约数是多少"，没有告诉我们怎么用 a、b 凑出这个最大公约数。扩展欧几里得算法（Extended Euclidean Algorithm，简称 ExGCD）在求 gcd(a,b) 的同时，还能求出一组整数解 x, y，满足：
a×x + b×y = gcd(a, b)
这样的整数解 x, y 一定存在（这是数论里的裴蜀定理），扩展欧几里得算法能把它们具体求出来。这个结果是后面求逆元（本节 ④）、解线性同余方程等一系列数论问题的基础工具。
回忆欧几里得算法的递归关系：gcd(a,b) = gcd(b, a mod b)，递归到 b=0 时，gcd(a,0)=a。扩展欧几里得在这个递归的基础上，多带一步"回溯"：假设已经递归算出了 b×x₁ + (a mod b)×y₁ = gcd(b, a mod b)，可以推出一组满足 a×x + b×y = gcd(a,b) 的 x, y——递归返回的过程中，把子问题的解"翻译"成当前问题的解。
| 推导步骤 | 内容 |
|---|---|
| 已知 | b×x₁ + (a mod b)×y₁ = gcd(b, a mod b) = gcd(a, b) |
| 代入 a mod b = a - (a/b)×b | b×x₁ + (a - (a/b)×b)×y₁ = gcd(a, b) |
| 展开、按 a、b 重新归类 | a×y₁ + b×(x₁ - (a/b)×y₁) = gcd(a, b) |
| 对照 a×x+b×y=gcd(a,b) | x = y₁，y = x₁ - (a/b)×y₁ |
递归求解 ExGCD(30, 18)，先一路递归到底（和普通欧几里得算法的过程一样），再逐层回溯计算 x, y：
| 调用 | a mod b | gcd | 回溯算出的 x, y |
|---|---|---|---|
| ExGCD(6, 0) | —（b=0，递归到底） | 6 | x=1, y=0 |
| ExGCD(12, 6) | 12 mod 6 = 0 | 6 | x=y₁=0，y=x₁-(12/6)×y₁=1-2×0=1 |
| ExGCD(18, 12) | 18 mod 12 = 6 | 6 | x=y₁=1，y=x₁-(18/12)×y₁=0-1×1=-1 |
| ExGCD(30, 18) | 30 mod 18 = 12 | 6 | x=y₁=-1，y=x₁-(30/18)×y₁=1-1×(-1)=2 |
x=-1，y=2：验证一下 30×(-1) + 18×2 = -30+36 = 6，正好等于 gcd(30,18)=6。整个过程只在最底层（b=0）直接给出解 (x=1,y=0)，之后每一层回溯都只是套用②推导出的公式，不需要重新计算。在普通实数运算里，a 除以 b 等于 a 乘以 b 的倒数 1/b。但在模运算的世界里没有"分数"这回事——如果需要在模 m 的意义下"除以 a"，就要找到 a 的逆元 a⁻¹，满足：
a × a⁻¹ ≡ 1 (mod m)
求出 a⁻¹ 之后，"除以 a"就可以换成"乘以 a⁻¹"来处理——这在很多需要"对大数取模"的组合数学、概率类问题里非常常用（比如算出一个很大的分数结果，要求对 10⁹+7 取模）。逆元存在的条件是 gcd(a, m) = 1（a 和 m 互质），否则逆元不存在。
求逆元的方法：把 a×a⁻¹ ≡ 1 (mod m) 改写成 a×x + m×y = 1（这里 gcd(a,m)=1），用 ExGCD 求出的 x 就是答案（如果 x 是负数，加上 m 调整到 [0, m) 范围内）。以求 3 关于模 7 的逆元为例：ExGCD(3, 7) 算出 x=-2，y=1（验证：3×(-2)+7×1=-6+7=1），调整负数：-2 mod 7 = 5。验证 3×5=15=14+1≡1 (mod 7)，3 关于模 7 的逆元是 5。
| 1 | // 求 a、b 的最大公约数，同时算出满足 a*x+b*y=gcd(a,b) 的 x, y（引用传参带回结果） |
| 2 | int ExGCD(int a, int b, int& x, int& y) |
| 3 | { |
| 4 | if (b == 0) { x = 1; y = 0; return a; } // ★ 递归到底：gcd(a,0)=a，此时 x=1,y=0 |
| 5 | int x1, y1; |
| 6 | int g = ExGCD(b, a % b, x1, y1); // 先递归求子问题 |
| 7 | x = y1; // ★ 回溯：套用②推导出的公式 |
| 8 | y = x1 - (a / b) * y1; |
| 9 | return g; |
| 10 | } |
| 11 | |
| 12 | // 求 a 关于模 m 的逆元；返回 -1 表示逆元不存在（a、m 不互质） |
| 13 | int Inverse(int a, int m) |
| 14 | { |
| 15 | int x, y; |
| 16 | int g = ExGCD(a, m, x, y); |
| 17 | if (g != 1) return -1; // ★ 不互质，逆元不存在 |
| 18 | return ((x % m) + m) % m; // ★ 调整到 [0, m) 范围内 |
| 19 | } |
m 恰好是质数，可以证明 a^(m-2) mod m 就是 a 的逆元，用 1.7 节学过的快速幂就能求出来，代码比 ExGCD 更短。但这个方法要求 m 必须是质数；如果 m 不是质数（只要求 gcd(a,m)=1），就必须用本节的 ExGCD 方法，适用范围更广。a、m 不互质，逆元根本不存在——ExGCD 依然会返回一组 x,y，但满足的是 a×x+m×y=gcd(a,m)（不是 1），直接拿这个 x 当逆元用会得到错误结果。必须先判断第 17 行的 g==1，再决定逆元是否存在。x（比如本节例子里的 -2）在数学上是正确的解，但作为"模 m 意义下的逆元"，通常要求落在 [0, m) 这个范围内。第 18 行 ((x % m) + m) % m 这个写法，和 17.1 节字符串哈希处理负数取模的技巧是同一个道理——先加一个 m 再取模，确保结果非负。