【数论】扩展欧几里得算法

转载自：exgcd详解 - zzt1208 - 博客园 (cnblogs.com)

1.exgcd是什么？

exgcd大名扩展欧几里得算法，用来求形如 $ax+by=gcd(a,b)$（$a,b$ 为常数）的方程的一组整数解。

---

2.推导

当 $b=0$ 时，$gcd(a,b)=a$，此时 $x=1$， $y=0$

当 $b≠0$ 时，考虑到 $gcd(a,b)=gcd(b,a\ mod\ b)$，所以我们可以先递归去求 $bx+(a\ mod\ b)y=gcd(b,a\ mod\ b)$ 的解

$$\begin{cases} x=x_0 \\ y=y_0 \end{cases}$$

然后再往回带：

$$\begin{aligned} ax+by&=gcd(a, b) \\ &=gcd(b,a\ mod\ b) \\ &=bx_0+(a\ mod\ b)y_0 \end{aligned}$$

因为 $a\ mod\ b=a−⌊\frac{a}{b}⌋b$，所以：

$$\begin{aligned} ax+by&=bx_0+(a−⌊\frac{a}{b}⌋b)y_0 \\ &=bx_0+ay_0−⌊\frac{a}{b}⌋by_0\\ &=ay_0+b(x_0−⌊\frac{a}{b}⌋y_0) \end{aligned}$$

即方程 $gcd(a,b)=ax+by$ 的一个解为 $x=y_0,y=x_0−⌊\frac{a}{b}⌋y_0$

//公式是我一个字一个字手敲的，要敲断了……

---

3.代码实现

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