什么是拓展欧几里得?简单的说,就是求关于x,y的方程 ax + by = gcd(a,b) 的所有整数解
现在我们来解决一下三个问题
我们都知道,欧几里得公式可以由这个式子表达
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,一加一减,最终不变
如果 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; }
参考博客