重新整理一下扩欧。
扩展欧几里得就是欧几里得算法也就是辗转相除法的扩展应用，扩展后的作用主要为求二元一次方程组的一个解。
基本原理
众所周知，一个式子是无法确定两个未知数的唯一值的，因此 exgcd 只能解出一种符合要求的解，但是因为有通解的存在，你可以由这个解推出其他所有的可能解。
先看看扩展的地方，欧几里得的原理是 \(\gcd(a,b) = \gcd(b, a\bmod b)\)，设 \(\gcd(a, b) = d\) 我们可以到一个式子 \(ax + by = d\)（来自裴蜀定理），根据辗转相除法的原理，我们会不断将 \(a,b\) 辗转相除，直到一个数为 \(0\)（设这个数为 \(b'\)），但此时上面的式子依旧成立，即 \(a'x' + 0 \times y' = d\)，也就是 \(a'x' = d\)，根据辗转相除法的原理，此时 \(a'\) 就是求得的最大公约数。此时我们就可以知道，\(a'x' = d\) 中的 \(x'\) 应该为 \(1\)，而 \(y'\) 可以为任意数（\(0\) 乘任何数都是 \(0\)，一般取 \(0\)）。现在，你已经求出了一个符合的 \(x',y'\)，而这个值我们可以回代，就可以求出最初 \(ax + by = d\) 中的 \(x,y\)。
该怎么回代呢，这里比较抽象，我们想一想，辗转完一次后的 \(a',b'\) 分别等于多少呢？看看辗转相除法的代码。
int gcd(int a, int b)
{
return b ? a : gcd(b, a % b);
}
可以发现我们向下传的 \(a',b'\) 其实就是 \(b,a \bmod b\)。那么我们等式 \(a'x' + b'y' = d\) 就变为了，\(bx' + (a \bmod b)y' = d\)，我们也知道 \(a \bmod b = a - \lfloor \frac{a}{b} \rfloor \times b\)，那么式子就可以进一步化为
\[bx' + ay' - \lfloor \frac{a}{b} \rfloor \times by' = d \]整理可得
\[ay' + b(x' - \lfloor \frac{a}{b} \rfloor y') = d \]而我们之前的式子有
\[ax + by = d \]这就产生对应关系了，如果我们知道一种 \(x',y'\) 的值，就可以求出一种 \(x,y\) 的值，对应关系即为
\[\begin{aligned} x &= y' \\ y &= x' - \lfloor \frac{a}{b} \rfloor y' \end{aligned} \]还记得上面说的，我们可以求出最后一个 x',y' 的值吗，既然有了关系，那么就可以回代了。
代码实现
然后就是代码中的实现方式，为了把后面的 \(x',y'\) 传上来，我们需要用取址，在最后还要特判 \(b = 0\) 时，把此时的 \(x,y\) 赋值。对于之前的 \(x,y\) 我们就根据关系来求出即可，而这一步，就是本文重点。
我们可以写出如下代码
int exgcd(int a, int b, int &x, int &y)
{
if (b == 0)
{
x = 1;
y = 0;
return a;
}
int d = exgcd(b, a % b, x, y);
int tx = x, ty = y; // 即x',y'
y = tx - a / b * ty;
x = ty;
return d;
}
但实际上代码还可以精简，因为是用传址带回来的 \(x',y'\)，在当前 \(x,y\) 还没更新时，有 \(x = x'\) 和 \(y = y'\)，这样的关系，因此可以直接用 \(x,y\) 代替代码中 \(tx,ty\)，则有新代码
int exgcd(int a, int b, int &x, int &y)
{
if (b == 0)
{
x = 1;
y = 0;
return a;
}
int d = exgcd(b, a % b, x, y);
int t = y;
y = x - a / b * t;
x = t;
return d;
}
但这还不是我们最常用的，众所周知，辗转相除法在代码实现上为了让 \(a,b\) 互换位置辗转相除，在递归上是 gcd(b, a % b)，而不是 gcd(a % b, b)。这里我们可以借鉴思想，把扩展欧几里得里面的 \(x,y\) 在递归下一层时换位。这样有什么好处？此时
在求出当前 \(x,y\) 时就变成了
\[\begin{aligned} x &= y' = x \\ y &= x' - \lfloor \frac{a}{b} \rfloor y' = y - \lfloor \frac{a}{b} \rfloor x \end{aligned} \]你会发现，\(x\) 我直接不用变了，而 \(y\) 我直接自减即可，不用定义新变量，更简洁，于是得到了代码
int exgcd(int a, int b, int &x, int &y)
{
if (b == 0)
{
x = 1;
y = 0;
return a;
}
int d = exgcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
而这就是我们最常用的扩展欧几里得代码。
至此，本文结束。
标签：lfloor,return,gcd,int,欧几里得,扩展,exgcd,代码 From： https://www.cnblogs.com/blind5883/p/18224288