扩展欧几里得算法CSP-S

💡 核心思想

扩展欧几里得算法（exgcd）不仅能求两个数的最大公约数 gcd(a,b)，还能找到一组整数解 (x, y) 满足贝祖等式 ax + by = gcd(a,b)。这是求解线性同余方程、模逆元（当 a,b 互质时）和中国剩余定理的基础工具。

🎯 直觉理解

普通欧几里得算法是"辗转相除求最大公约数"，而扩展版还顺便记录了"如何用 a 和 b 组合出这个公约数"。想象你有两个不同容量的水桶，exgcd 不仅告诉你它们能精确量出的最小水量（gcd），还告诉你具体要倒几次 A 桶、倒几次 B 桶才能量出来。

📝 算法流程

1. 递归边界：当 b = 0 时，gcd(a, 0) = a，此时 x = 1, y = 0
2. 递归调用：exgcd(b, a % b)，得到解 (x₁, y₁) 满足 bx₁ + (a % b)y₁ = gcd
3. 回代：a % b = a - ⌊a/b⌋ × b，代入得 ay₁ + b(x₁ - ⌊a/b⌋y₁) = gcd
4. 因此 x = y₁, y = x₁ - ⌊a/b⌋y₁
5. 若求 ax ≡ 1 (mod m) 的逆元：先用 exgcd(a, m) 得 ax + my = 1，则 x mod m 就是逆元

$$ax + by = gcd(a,b)$$

$$\text{若 }gcd(a,m)=1,\text{ 则 }a\text{ 在模 }m\text{ 下的逆元为 }(x \bmod m + m) \bmod m$$

📊 复杂度分析

💻 参考实现（C++）

#include 
using namespace std;
using ll = long long;

// 扩展欧几里得：返回 gcd(a,b)，并求出满足 ax + by = gcd 的 x, y
ll exgcd(ll a, ll b, ll &x, ll &y) {
    if (b == 0) { x = 1; y = 0; return a; }
    ll x1, y1;
    ll g = exgcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return g;
}

// 求 a 在模 mod 下的乘法逆元（要求 gcd(a, mod) = 1）
ll modInverse(ll a, ll mod) {
    ll x, y;
    ll g = exgcd(a, mod, x, y);
    if (g != 1) return -1; // 逆元不存在
    return (x % mod + mod) % mod;
}

// 解线性同余方程 ax ≡ c (mod m)
bool linearCongruence(ll a, ll c, ll m, ll &x0, ll &step) {
    ll x, y;
    ll g = exgcd(a, m, x, y);
    if (c % g != 0) return false; // 无解
    ll t = m / g;
    x0 = (x * (c / g) % t + t) % t; // 最小非负解
    step = t; // 通解：x = x0 + k * step
    return true;
}

int main() {
    ll x, y;
    
    // 1. 求 30x + 12y = gcd(30, 12) = 6
    ll g = exgcd(30, 12, x, y);
    cout << "gcd = " << g << ", x = " << x << ", y = " << y << endl;
    // 验证：30*(-1) + 12*3 = -30 + 36 = 6 ✓
    
    // 2. 求 7 在模 13 下的逆元
    ll inv = modInverse(7, 13);
    cout << "inv(7, 13) = " << inv << endl;
    cout << "7 * " << inv << " % 13 = " << (7 * inv % 13) << endl;
    
    // 3. 解 6x ≡ 4 (mod 10)
    ll x0, step;
    if (linearCongruence(6, 4, 10, x0, step))
        cout << "x ≡ " << x0 << " (mod " << step << ")" << endl; // x ≡ 4 (mod 5)
    else
        cout << "No solution" << endl;
    
    return 0;
}

⚠️ 常见坑点

📚 相关题目