扩展欧几里得

窝们可以先来看一个式子：

\[ax + by = gc d(a,b) \]

根据欧几里得可以得到：

不会欧几里得的同学们可以看这里

又根据原式可以推出 :

所以可以得到：

再化简，得：

运用主元法，可得：

窝们把 \(a, b\) 当作元，再来重新来看这个问题。

对于一个丢番图方程，\(a * x + b * y = a_1 * x_1 + b_2 * y_1\)

是不是肯定会有这样一组解：\(a = a_1\) 且 \(b = b_2\)

那么原方程是不是肯定会有一个这样的根：

\[x = y_1 \\ y = x_1 - \frac{a}{b} * y_1 \]

如果你可以理解上面这些步骤，那么你肯定可以知道这个 \(x, y\) 是可以递归求解的。只不过要处理一下 \(-\frac{a}{b} * y_1\)

那么,窝们先来看看代码怎么实现，说不定看完你就懂了。

void exgcd(int a, int b, int &x, int &y) {
    if(b == 0) {x = 1, y = 0; return a;}//这个是一个必然存在的解，后面解释。
    exgcd(b, a % b, y, x);//这是不断递归，窝们前面对于y的变换法则中，窝们只管了x1，后面那个式子先不管他，至于前面这个a,b为什么要这样递归，是因为窝们转换原方程的时候是借助了欧几里得，所以窝们这个式子递归的时候也需要改变a,b。让a1,b1变成b,a % b;
    y -= (a / b) * x;//这里再来处理y转移的时候后面的那一部分。直接在递归的过程中去减去就行了，由于减完后这一层就直接结束了，所以不会影响其他 % 运算……运算的结果。
}

这里再来解释一下为什么 \(b == 0\) 的时候，原方程必有根。

如果 \(b == 0\) :

那么原式就可以化成这个样子：

那么这个式子中，如果 \(x == 1\) 肯定会有 :

此时， \(y\) 可以取任意值，所以在那个里面的 \(y\) 不一定要赋值为 \(0\)； \(1\), \(2\), \(3\)都可以，不过赋值为 \(0\) 是最小的。

既然已经知道了\(b == 0\) 的时候必然有解，又可以理解前面的方程转化的过程，那么恭喜你，你证完扩展欧几里得辣！！！

你太巨辣！！！