学习笔记目录
有任何问题，欢迎私信/评论。
码字不易，求点赞啦~

扩展欧几里得

问题：给定整数 $a,b$，令 $d=gcd(a,b)$，解方程：$ax+by=d$。

先从 $gcd$ 入手，我们知道 $gcd(a,b)=gcd(b,a\% b)$，那么显然，$ax+by=bx+(a\% b)y=d$。假设我们求解出了方程 $bx+(a\% b)y=d$ 的一组解：$x=x_0,y=y_0$，那么原方程的解与 $x_0,y_0$ 间有什么关系呢？
$$ d=bx_0+(a\% b)y_0 $$
$$ d=bx_0+(a- \lfloor \dfrac{a}{b}\rfloor \times b)y_0 $$
$$ d=bx_0+ay_0-\lfloor \dfrac{a}{b}\rfloor \times b \times y_0 $$
$$ d=ay_0+b(x_0-\lfloor \dfrac{a}{b}\rfloor\times y_0) $$
我们再把上面这个狮子和 $ax+by=d$ 进行比对，发现原方程的一组特解就是 $x=y_0,y=x_0-\lfloor \dfrac{a}{b}\rfloor\times y_0$。

【代码】

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