※ 引述《nevikw39 (☆牜攵☆犬羊)》之铭言：
: 大家安安 o'_'o
: 最近在学习线性同余方程，不太了解所谓扩展欧几里得算法的过程。
: 以前学过一般欧几里得法 aka 辗转相除法，现在这个扩展推广我明白所求是解出 a * x + b * y = gcd(a, b)。
: 以下是我根据网络查出的写法：
: int exgcd(int a, int b, int &x, int &y)
: {
: if (!b)
: {
: x = 1;
: y = 0;
: return a;
: }
: int g = exgcd(b, a % b, y, x);
: y -= a / b * x;
: return g;
: }
: if 内的叙述我可以理解：当 b = 0 时 gcd(a, b) = a，此时 a*1 + b*0 = gcd(a, b)
: if 后的部分我就不太懂惹，如果算出 b*y' + (a%b)*x' = gcd(a, b)，则如何求出
: a * _ + b * _ = gcd(a, b) ??
: y -= a / b * x 的意义是什么呢？？
: 感谢大家
a 除以 b 的商为 a / b, 余为 a % b (这里我把 / 当成整数除法)
也就是说我们有 a % b = a - (a / b) * b (余数 = 被除数 - 商 * 除数)
那么代入 gcd(a, b) = b*y' + (a%b)*x'
= b*y' + [a - (a/b) * b]*x'
= b*y' + a*x' - (a/b)*b*x'
= a*x' + b*(y' - (a/b)*x)
﹌﹌﹌↑﹌﹌﹌
这就是新的 y 了