C++如何使用扩展欧几里得算法求模逆元-C++-PHP中文网

模逆元 $ a^{-1} \bmod m $ 存在当且仅当 $ \gcd(a, m) = 1 $，即 $ a $ 与 $ m $ 互质；这是逆元存在的充要条件，不满足则无解，不可强行计算。

c++如何使用扩展欧几里得算法求模逆元

模逆元存在的前提是什么

模逆元 a⁻¹ mod m 存在，当且仅当 gcd(a, m) == 1。这不是可选条件，而是数学硬约束——如果 gcd(a, m) != 1，extend_gcd 虽然仍能跑出结果，但那个结果不能当作模逆元用。实际编码时必须先检查，否则后续计算全错。

用 __gcd(a, m)（GCC）或自己写 gcd() 判断
若不互质，直接返回错误码（如 -1）或抛异常，别试图“强行取模”
注意：负数取模行为依赖语言实现，C++ 中 a % m 符号随 a，所以建议先做 a = (a % m + m) % m 归一化

如何用 extend_gcd 得到正确的逆元值

扩展欧几里得算法解的是 a x + m y = gcd(a, m)。当 gcd(a, m) == 1 时，该式变为 a x + m y = 1，两边对 m 取模，立刻得到 a * x ≡ 1 (mod m)，所以 x 就是逆元——但这个 x 可能为负或大于 m。

调用后必须对 x 做模调整：x = (x % m + m) % m
不要只写 (x % m)：C++ 中 -5 % 7 是 -5，不是 2
extend_gcd 返回的 x 和 y 是任意一组解，通解是 x + k*m，所以调整一次就够了

long long extend_gcd(long long a, long long b, long long &x, long long &y) {
    if (b == 0) {
        x = 1; y = 0;
        return a;
    }
    long long g = extend_gcd(b, a % b, y, x);
    y -= a / b * x;
    return g;
}
<p>long long mod_inv(long long a, long long m) {
long long x, y;
long long g = extend_gcd(a, m, x, y);
if (g != 1) return -1; // 无逆元
return (x % m + m) % m;
}</p>