扩展欧几里得算法¶

欧几里得算法的扩展，能在计算 \(\gcd(a,b)\) 的同时，求出对应裴蜀等式 \(ax+by=\gcd(a,b)\) 的一组解。

原理¶

欧几里得算法的核心公式是

根据裴蜀定理，一定 \(\exists x_1,y_1,x_2,y_2 \in \mathbb{Z}\)，使得

根据模运算定义，\(a \bmod b = a-bq\)，\(q\) 是 \(a/b\) 的商，所以

推得

如果在递归的某一层算出了一组解，就能通过上面的公式倒推回去，算出最终的答案。欧几里得算法的终止条件是 \(b=0\)，此时显然有一组解 \(x=1,y=0\)。

递归实现¶

理论上，a / b 的商的计算要与 a % b 的实现一致。参考：模运算 > 余数的符号。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

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, x, y);
    int t = x;
    x = y;
    y = t - (a / b) * y;
    return d;
}

参考¶

（扩展）欧几里得算法 - 知乎 (zhihu.com)