拓展欧几里得$(exgcd)$算法是用于解决$ax+by=gcd(a,b)$的一种算法。

我们设：$$ax_1+by_1=d=gcd(a,b)\cdots1 $$$$bx_2 +(a\%b)y_2=gcd(b,a\%b)\cdots2$$ 由$\%$运算性质可得：$$gcd(a,b)=gcd(b,a\%b)$$ 则可得：$$ax_1+by_1=bx_2+(a\%b)y_2$$ 而在C++中，$/$表示整除运算，由$\%$的运算性质可得：$$\Rightarrow ax_1+by_1=bx_2+(a-a/b\times b)y_2$$$$\Rightarrow ax_1+by_1=ay_2+b(x_2-a/b\times y_2)\;\;(\text{欧几里得算法})$$ 显然可以得出：$$\Rightarrow x_1=y_2,\;y_1=x_2-a/b\times y_2$$ 特别地，我们定义当$b=0$时，$gcd(a,b)=a$，也就是辗转相除法中当$a\mod b=r=0$时，$gcd(a,b)=b$。此时$x=1,y=0$。这是递归边界。

当$ax+by=1$，$gcd(a,b)=d=1$，所以：$$(ax)\mod b=(1-by)\mod b=1 \mod b$$$$\Rightarrow x \text{的解就是a关于模b的逆元}.$$$$\text{同理可得}y\text{的解就是b关于模a的逆元}.$$ 这种方法仅可用于$a\equiv 1(\mod b)$的情况！

代码

#include<bits/stdc++.h>
using namespace std;

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

int main() {
    int a, b, x, y;
    scanf("%d%d", &a, &b);
    int gcd = ExGcd(a, b, x, y);
    printf("x=%d y=%d gcd=%d\n", x, y, gcd);
    return 0;
}