闲话

这个笔记就简单证一下扩欧的原理吧。顺便知道了这个就可以知道裴蜀定理一定成立。

题目大意

求 $ax+by=\gcd(a,b)$ 的一组特解。

思路

通过辗转相除法可以知道 $\gcd(a,b)=\gcd(b,a\bmod b)$。所以可以往下扩展。

$\because \gcd(a,b)=\gcd(b,a\bmod b),ax_2+by_2=\gcd(b,a\bmod b)$

$\therefore ax_1+by_1=bx_2+(a\bmod b)y_2=\gcd(b,a\mod b)=\gcd(a,b)$

$\because a\bmod b=a-(\lfloor \frac{a}{b}\rfloor \cdot b)$

$\therefore bx_2+(a\bmod b)y_2=bx_2+(a-(\lfloor \frac{a}{b}\rfloor \cdot b))x_2$

$ax_1+by_1=bx_2+ay_2-\lfloor \frac{a}{b}\rfloor \cdot by_2$

$ax_1+by_1=ay_2+b(x_2-\lfloor \frac{a}{b}\rfloor y2)$

$\Longrightarrow x_1=y_2,y_1=x_2-\lfloor \frac{a}{b}\rfloor y2$

另外显然在 $b=0$ 时 $x=1,y=0$，所以做 $\gcd$ 达到边界后返回往上带就行了。

裴蜀定理就主要证明了一定有一组特解。其实从扩欧中就可以看出来，因为一定有最大公约数，所以一定能带上来。

代码

ll exgcd(ll a, ll b, ll &x, ll &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    ll d = exgcd(b, a % b, x, y);
    ll X = x;
    x = y;
    y = X - (a / b) * y;
    return d;
}

总结

证明了扩欧的原理。