什么是拓展欧几里得？简单的说，就是求关于x,y的方程 ax + by = gcd(a,b) 的所有整数解
现在我们来解决一下三个问题
- 怎么求上述方程的特解？
- 怎么求由特解推出其他的所有解？
- 如何求的是ax + by = c，则解为什么？
一、求特解
我们都知道，欧几里得公式可以由这个式子表达
gcd(a, b) = gcd(b, a % b)
通过这个式子，我们可以不断递推到b = 0， 此时a即为a和b的最大公约数
现在我们对这个式子进行展开，看看有什么好玩的嘛
gcd(a, b) = a * x1 + b * x2
gcd(b, a % b) = b * x2 + (a % b) * y2
其中a % b = a - (a / b) * b
故由第一行的欧几里得公式得：
a * x1 + b * y1 = b * x2 + {a - (a / b) * b}y2
化简得a * x1 + b * y1 = a * y2 + b * {x2 - (a / b) * y2}
根据待定系数法得到
-
x1 = y2
-
y1 = x2 - (a / b) * y2
也就是说，如果有了gcd(b, a % b)的解x2, y2就可以推出gcd(a, b)的解x1, y1
那么这就和求gcd的过程一样，一直推到最后x = 1， y = 0，就可以回溯回去，得到gcd(a, b)的特解x1, y1
特解其实是最小的一个解
二、怎么利用特解推出其他所有整数解
先说结论：
x = x 0 + k ∗ b g c d ( a , b ) x = x0 + k * \frac{b}{gcd(a,b)} x=x0+k∗gcd(a,b)b
y = y 0 − k ∗ a g c d ( a , b ) y = y0 - k * \frac{a}{gcd(a,b)} y=y0−k∗gcd(a,b)a
x0, y0就是方程的特解
对于a * x + b * y = g来说，让x增加b/gcd,让y增加a / gcd
这样就相当于加a * b / gcd，减去a * b / gcd,一加一减，最终不变
三、如何求的是ax + by = c,则解是什么？
如果 c % gcd(a, b) == 0，即c 是 gcd(a, b)的整数倍，则方程有解，且解就在上面的基础上乘以 c g c d ( a , b ) \frac{c}{gcd(a, b)} gcd(a,b)c即可
void e_gcd(int a, int b, int &gcd, int &x, int &y)
{
if (b == 0)
{
x = 1;
y = 0;
gcd = a;
}
else
{
e_gcd(b, a % b, gcd, y, x);
y -= x * (a / b);
}
}
int main(){
int a, b, x, y, gcd;
cin>>a>>b;
e_gcd(a, b, gcd, x, y);
cout<<x<<' '<<y<<endl;
cout<<gcd<<endl;
return 0;
}