扩展欧几里得定理

已知 $(a,b)=d$ 是 a，b 的最大公约数d。

而扩展欧几里得可以确定 $ax+by=d$ 的系数 $x,y$ 。

推理过程：

$(a,b)=(b,a\mathrm{mod}b)$ 即 $xb+y(a\mathrm{mod}b)=d$ 进行取模拆分： $xb+y(a-\frac{a}{b}\times b)=d$ $xb+ay-\frac{a}{b}\times b\times y=d$ 合并后： $ay+b(x-\frac{a}{b}y)=d$ 故转化后的 $x^{\prime }=y,y^{\prime }=x-\frac{a}{b}y$

可以直接递归时 $exgcd(y,x)$ , 这样传入的就直接是 $x^{\prime }=y$ 之后直接更新 $y-=\frac{a}{b}y$

求出一组解 $x_0,y_0$ 后， 其他所有解都满足此形式： $x=x_0+k(\frac{a}{b})$ $y=y_0-k(\frac{a}{b})$ $k\subset Z$