模逆元a⁻¹ mod m存在的充要条件是gcd(a, m) = 1；若不满足，扩展欧几里得算法虽能解出ax + my = g，但x不是模逆元，必须先验证g == 1再归一化x到[0, m)区间。
扩展欧几里得算法能求模逆元的前提是什么
模逆元 a⁻¹ mod m 存在，当且仅当 gcd(a, m) == 1。这不是算法能绕开的数学约束——如果 gcd(a, m) != 1，ax ≡ 1 (mod m) 无解，调用扩展欧几里得也只会返回一个满足 ax + my = g 的 x，但这个 x 不是模逆元。
常见错误现象：inv = exgcd(a, m).first 直接当逆元用，却不检查 g == 1；结果代入验证时 (a * inv) % m 不等于 1。
使用场景：RSA 密钥生成、椭圆曲线标量乘中的除法替换、NTT 中的单位根逆元计算。
必须做两件事：
- 调用 exgcd(a, m, x, y)（传引用输出 x, y）
- 检查返回值 g 是否为 1；不是就报错或返回非法值（如 -1）
- 若是，取 (x % m + m) % m 归一化到 [0, m) 区间
标准 exgcd 函数怎么写才不爆 int / 不错位
C++ 里最简健壮实现要处理符号和溢出边界。递归版易栈溢出，迭代版更安全；且所有中间变量建议用 long long，尤其当 a 和 m 接近 INT_MAX 时，a % b 和减法可能隐式溢出。
立即学习“C++免费学习笔记（深入）”；
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
迭代版关键点：
- 初始：r0 = a, r1 = m, s0 = 1, s1 = 0, t0 = 0, t1 = 1
- 循环条件是 r1 != 0，每次更新：q = r0 / r1，然后 r2 = r0 - q * r1 等
- 最终 g = r0，x = s0，y = t0
- 返回前对 x 做模调整：x = (x % m + m) % m，否则可能是负数
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, y, x);
y -= a / b * x;
return g;
}
注意：这个递归版本中 y, x 顺序交换是为了省去额外变量，但初学者容易看错——它依赖参数传递顺序和引用绑定，不如迭代版直觉。
为什么 (x % m + m) % m 不可省略
exgcd 返回的 x 满足 a<em>x + m</em>y == g，但它只是贝祖系数之一，范围完全不确定。例如 exgcd(3, 11) 可能返回 x = 4（正确），但也可能返回 x = -7（因为 3<em>(-7) + 11</em>2 = -21 + 22 = 1）。而模逆元定义要求在 [0, m) 内唯一。
错误写法：
- int inv = x % m → 负数取模在 C++ 中仍是负数（如 -7 % 11 == -7）
- int inv = x % m + m → 若 x 是正数，可能越界（如 x = 15, m = 11 ⇒ 15 % 11 + 11 = 4 + 11 = 15，超范围）
- 正确：先取余再加模再取余，强制归一：(x % m + m) % m
实际调用时容易漏掉的边界检查
最常被跳过的三件事：
-
m <= 1：模数必须 ≥ 2，否则% m未定义或无意义
-
a < 0：允许负数输入，但应先做a = (a % m + m) % m归一化，否则exgcd可能返回异常大的负x
-
a == 0：直接无逆元，gcd(0, m) == m，除非m == 1（但此时模 1 无实际用途）
性能影响：exgcd 时间复杂度是 O(log min(a,m))，和普通欧几里得一致，没有额外开销。但若频繁调用，可考虑预计算或缓存小模数下的逆元表。
真正麻烦的是模数不固定、且无法提前保证互质的场景——这时不能只靠一次 exgcd，得配合 gcd 检查，或者改用其他机制（如 Montgomery 逆元要求模数奇数，但不检查互质）。
