\(\text{exgcd}\) 模板题

首先，我们需要知道 \(\text{B}\acute{e}\text{zout}\) 定理：对于任意整数 \(a,b\)，存在一对整数 \(x,y\)，满足 \(ax+by=\gcd(a,b)\)。

证明（部分摘自蓝书）：

在欧几里得算法（辗转相除法）的最后一步，即 \(b=0\) 时，显然有 \(x=1,y=0\)，使得 \(a\times1+b\times0=\gcd(a,0)\)。

若 \(b>0\)，则 \(\gcd(a,b)=\gcd(b,a\bmod b)\)。假设存在一对整数 \(x,y\)，满足 \(bx+(a\bmod b)y=\gcd(b,a\bmod b)\)，因为

\[bx+(a\bmod b)y=bx+(a-b\lfloor\dfrac{a}{b}\rfloor)y=ay-b(x-\lfloor\dfrac{a}{b}\rfloor y) \]

所以令 \(x'=y,y'=x-\lfloor\dfrac{a}{b}\rfloor y\)，就得到了 \(ax'+by'=\gcd(a,b)\)。

在欧几里得算法的递归中应用数学归纳法，可知 \(\text{B}\acute{e}\text{zout}\) 定理成立。

\(\huge{证毕}\)

由此可得到代码：

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

对于每个询问，由求出的 \(x,y\) 得出一组解即可，如 x y ax+by。