扩展欧几里得 | exgcd

在 $ax+by=gcd(a,b)$ 中：

1. 求解过程中始终有 $|x| \leq |b|$ , $|y| \leq |a|$。

   证明如下：

   

2. 设 $|a| \geq |b|$ , 则求出的 x 满足 $|x|$ 最小。

   证明如下：

   

其实代自己码中的exgcd 不满足上述条件（小心被 *** 诈骗）。