扩展欧几里得算法

扩展欧几里得算法是欧几里得算法的扩展，用于在已知 $a$, $b$ 的情况下求解一组 $x$, $y$，使得他们满足裴蜀定理 $ax + by = gcd(a, b)$

裴蜀定理

若 $a, b$ 是整数，且 $\gcd(a, b) = d$，那么对于任意整数 $x, y, ax+by = c$ 一定是 $d$ 的倍数
特别地，一定存在整数 $x, y$，使得$ax + by = d$ 成立

扩展欧几里得算法常用与得出线性方程 $ax+by=c$ 的一组解（不难证明，当 $c\neq k\gcd(a, b)$ 时，方程无整数解）

算法流程

我们设 $a > b$

显然，当 $b = 0$ 的时候，$\gcd(a, b)=a$，此时 $x=1,\ y = 0$

当 $a > b > 0$ 时，设 $ax_1 + by_1 = \gcd(a, b)$，$bx_2 + (a\ mod\ b)y_2 = \gcd(b, a\ mod\ b)$

根据欧几里得定理，有 $\gcd(a, b) = \gcd(a, a\ mod\ b)$

将式子合并，$ax_1 + by_1 = \gcd(a, b) \Rightarrow b(\left\lfloor\frac{a}{b}\right\rfloor x_1 + y_1) + (a\ mod\ b)x_1 = \gcd(a, b)$

将上式中的 $(\left\lfloor\frac{a}{b}\right\rfloor x_1 + y_1)$ 替换为 $x_2$，将第二项中的 $x_1$ 替换为 $y_2$，那么上式就变成了 $bx_2+(a\ mod\ b)y_2 = \gcd(a, a\ mod\ b)$

一直进行这个操作，和欧几里得定理一样，我们最终会碰到 $b = 0$ 时候，这时 $ax_n + 0y_n = \gcd(a, 0)$

我们将 $x_n$ 设为 $1$，$y_n$ 设为 $0$，递归回去，就能求出一开始的 $x_1$ 和 $y_1$，也就得到了方程 $ax_1 + by_1 = c$ 的一组解

将 $mod$ 运算转换为数学表示，有 $ax_1 + by_1 = bx_2 + (a mod b)y_2 = bx_2 + (a - [a / b] * b) y_2 = ay_2 + b(x_2 - [a / b] * by_2)$

即 $ax_1 + by_1 = ay_2 + b(x_2 - [a / b] * by_2)$

这样，我们就得到了一个递归求解 $x_1,\ y_1$ 的方法，并且在 $b = 0$ 时遇到递归边界 $x = 1, y = 0$

对于其余的整数解来说，我们只要求出一组解 $x, y$，就能通过 $x’ = x + k\frac{b}{\gcd(a,b)}$ 和 $y’ = y - k\frac{a}{\gcd(a,b)}$ 来得出其余的解（其实就是将后项的一部分移动到前项，或反向操作）

代码实现

int exgcd(int a, int b, int &x, int &y)
{
    if (b == 0) // 递归边界
    {
        x = 1;
        y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x); // 交换 x, y 满足 x1 = y2
    y -= (a / b) * x;               // 计算 y1 = x1 - [a/b]y2
    return d;
}