【数学】【模板】扩展欧几里得算法

标签：lfloor gcd int 欧几里得 算法 ax 模板

扩展欧几里得算法

思想

首先回忆一下裴蜀定理：对于任意一对不全为 \(0\) 的整数 \(a, b\)，存在 \(x, y\) 使得 \(ax + by = \gcd(a, b)\)。

扩展欧几里得算法就是求出一组解满足 \(ax + by = \gcd(a, b)\)，这里用到了欧几里得算法，不会的，可以看看我的博客。

我们看看怎么求：

1. 当 \(b = 0\) 的时候，\(ax = \gcd(a, b) = a\)，那么 \(x = 1\)。
2. 当 \(a \ne 0\) 且 \(b \ne 0\) 时，我们递归求解出 \((a\bmod b)x_1 + by_1 = \gcd(a, b)\) 后再计算 \(ax + by = \gcd(a, b)\)。

从 \(x_1, y_1\) 推出 \(x, y\)：

\[\begin{aligned} (a\bmod b)x_1 + by_1 &= \gcd(a, b)\\ (a - \left\lfloor\dfrac{a}{b} \right\rfloor\cdot b)x_1+by_1&= \gcd(a, b)\\ ax_1 - \left\lfloor\dfrac{a}{b} \right\rfloor\cdot bx_1+by_1&= \gcd(a, b)\\ ax_1+b(y_1 - \left\lfloor\dfrac{a}{b} \right\rfloor\cdot x_1) &= \gcd(a, b) \end{aligned} \]

所以 \(x = x_1, y = y_1 - \left\lfloor\dfrac{a}{b} \right\rfloor\cdot x_1\)。

然后就在欧几里得算法的时候顺便求出来了。

代码

int exgcd(int a, int b, int &x, int &y) {
    if (!b) {
        x = 1, y = 0;
        return a;
    }
    int g = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return g;
}

练习题

My Blog : AcWing 878. 线性同余方程题解

标签：lfloor,gcd,int,欧几里得,算法,ax,模板
From： https://www.cnblogs.com/Yuan-Jiawei/p/18315351