请注意,并不总是有解决方案。事实上,只有一个解决方案:c
是的倍数gcd(a, b)
.
也就是说,您可以使用扩展欧几里得算法为了这。
这是一个实现它的 C++ 函数,假设c = gcd(a, b)
。我更喜欢使用递归算法:
function extended_gcd(a, b)
if a mod b = 0
return {0, 1}
else
{x, y} := extended_gcd(b, a mod b)
return {y, x-(y*(a div b))}
int ExtendedGcd(int a, int b, int &x, int &y)
{
if (a % b == 0)
{
x = 0;
y = 1;
return b;
}
int newx, newy;
int ret = ExtendedGcd(b, a % b, newx, newy);
x = newy;
y = newx - newy * (a / b);
return ret;
}
现在如果你有c = k*gcd(a, b)
with k > 0
,方程变为:
ax + by = k*gcd(a, b) (1)
(a / k)x + (b / k)y = gcd(a, b) (2)
因此,只需找到 (2) 的解,或者找到 (1) 的解并乘以x
and y
by k
.