窝们可以先来看一个式子:
根据欧几里得可以得到:
\[gcd(a,b) = gcd(b, a \% b)\]
不会欧几里得的同学们可以看这里
又根据原式可以推出 :
\[gcd(b, a \% b) = b * x_1 + (a \% b) * y_1\]
所以可以得到:
\[a * x + b * y = b * x_1 + (a \% b) * y_1\]
再化简,得:
\[ x * a + y * b = x_1 * b + (a - (\frac{a}{b}) * b) * y_1\]
运用主元法,可得:
\[ x * a + y * b = y_1 * a + (x_1 - \frac{a}{b} * y_1) * b\]
窝们把 \(a, b\) 当作元,再来重新来看这个问题。
对于一个丢番图方程,\(a * x + b * y = a_1 * x_1 + b_2 * y_1\)
是不是肯定会有这样一组解:\(a = a_1\) 且 \(b = b_2\)
那么原方程是不是肯定会有一个这样的根:
如果你可以理解上面这些步骤,那么你肯定可以知道这个 \(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\) :
那么原式就可以化成这个样子:
\[a * x + 0 * y = gcd(a, 0) = a\]
那么这个式子中,如果 \(x == 1\) 肯定会有 :
\[x + 0 = x \ \ 原方程成立\]
此时, \(y\) 可以取任意值,所以在那个里面的 \(y\) 不一定要赋值为 \(0\); \(1\), \(2\), \(3\)都可以,不过赋值为 \(0\) 是最小的。
既然已经知道了\(b == 0\) 的时候必然有解,又可以理解前面的方程转化的过程,那么恭喜你,你证完扩展欧几里得辣!!!
你太巨辣!!!