扩展欧几里得算法 - NOI提高级教程

📖 扩展欧几里得核心推导

扩展欧几里得算法 (Extended Euclidean Algorithm) 在求最大公约数 $\gcd(a, b)$ 的同时，能找到一组整数解 $x, y$ 使得 $ax + by = \gcd(a, b)$。

📐 递归回溯系数转移推导

设我们对 $a$ 和 $b$ 调用递归。若在下一层 `extGcd(b, a % b, x1, y1)` 已经求得了满足方程的特解 $x_1, y_1$：

$b \cdot x_1 + (a \bmod b) \cdot y_1 = \gcd(b, a \bmod b) = d$

已知 $a \bmod b = a - \lfloor a/b \rfloor \cdot b$。带入上式：

$b \cdot x_1 + (a - \lfloor a/b \rfloor \cdot b) \cdot y_1 = d \implies a \cdot y_1 + b \cdot (x_1 - \lfloor a/b \rfloor \cdot y_1) = d$

与原方程 $ax + by = d$ 对照系数，即可得到回溯的状态转移方程：

$x = y_1, \quad y = x_1 - \lfloor a/b \rfloor \cdot y_1$

输入 a:

输入 b:

选择参数 $a$ 和 $b$，点击“递归回溯演示”查看递归树的层层探入和系数反代传递。

最大公约数 gcd(a, b) -

最终解 x & y -

递归深度 Depth -

方程检验 ax + by -

🌲 递归回溯状态树 (ExGCD Call Stack Tree)

long long extGcd(long long a, long long b, long long &x, long long &y) {
    if (b == 0) {
        x = 1; y = 0;
        return a;
    }
    long long x1, y1;
    long long d = extGcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return d;
}

📋 递归回溯日志