扩展欧几里得算法

• 在计算最大公约数时，顺便求出一组整数解$(x,y)$，使其满足$ax+by=\text{gcd}(a, b)$
• 拓展：方程$ax+by=d$有解的充要条件是$\text{gcd}(a, b) | d$
• 可用于求同余方程$ax\equiv d\left( \mathrm{mod}b \right) \Leftrightarrow \exists y\in \mathrm{Z},s.t. ax+by=d$，但注意，用ex_gcd(a, b, x, y)求得的x不是最终x，因为此时ex_gcd求出的x是满足的$ax+by=\text{gcd}(a,b)$的，而不是满足$ax+by=d$的，二者相差$d / \text{gcd}(a, b)$倍

证明 $\begin{aligned} ax+by&=\mathrm{gcd}\left( a,b \right) \\ &=gcd\left( b,a\mathrm{mod}b \right) \\ &=bx\prime+a\mathrm{mod}b\,\,y\prime \\ &=bx\prime+\left( a-\lfloor \frac{a}{b} \rfloor b \right) y\prime \\ &=bx\prime+ay\prime-\lfloor \frac{a}{b} \rfloor by\prime \\ &=ay\prime+b\left( x\prime-\lfloor \frac{a}{b} \rfloor b \right) \end{aligned}$ 对比$a$和$b$的系数得： $\begin{cases} x=y\prime\\ y=x\prime-\lfloor \frac{a}{b} \rfloor y\prime\\ \end{cases}$ 因此可根据递归得到的$x\prime$和$y\prime$计算$x$和$y$

代码

// 求x, y，使得ax + by = gcd(a, b)
int exgcd(int a, int b, int &x, int &y)
{
    if (!b)
    {
        x = 1; y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);      // 递归结束时，y = x'，x = y'
    y -= (a/b) * x;                    // y = x'-(a / b) * y' = y - (a / b) * x
    return d;
}

// 详细版
// 求x, y，使得ax + by = gcd(a, b)
int exgcd(int a, int b, int &x, int &y)
{
    if (!b)
    {
        x = 1; y = 0;
        return a;
    }
    int x_new, y_new;
    int res = exgcd(b, a % b, x_new, y_new);
    x = y_new;                      // x = y'
    y = x_new - (a/b) * x;           // y = x' - (a / b) * y'
    return res;
}