跳转至

扩展欧几里得算法

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

原理

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

\[ \gcd(a,b)=\gcd(b, a \bmod b) \]

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

\[ ax_1+by_1=\gcd(a,b)=\gcd(b, a \bmod b)=bx_2+(a \bmod b)y_2 \]

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

\[ \begin{align} ax_1+by_1&=bx_2+ \left (a-bq \right) y_2\\ &=ay_2+b\left (x_2 - q y_2 \right ) \end{align} \]

推得

\[ \left\{\begin{array}{l} x_1=y_2\\ y_1=x_2 - q y_2 \end{array}\right. \]

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

递归实现

理论上，a / b 的商的计算要与 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, x, y);
    int t = x;
    x = y;
    y = t - (a / b) * y;
    return d;
}

参考

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

相关文章