C++扩展欧几里得算法怎么求模逆元-C++-PHP中文网

模逆元a⁻¹ mod m存在的充要条件是gcd(a, m) = 1；若不满足，扩展欧几里得算法虽能解出ax + my = g，但x不是模逆元，必须先验证g == 1再归一化x到[0, m)区间。

c++扩展欧几里得算法怎么求模逆元

扩展欧几里得算法能求模逆元的前提是什么

模逆元 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 和减法可能隐式溢出。

迭代版关键点：
- 初始：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 顺序交换是为了省去额外变量，但初学者容易看错——它依赖参数传递顺序和引用绑定，不如迭代版直觉。

C++ Code Review Master

组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。

下载

为什么 (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