Обратите внимание, что не всегда есть решение.На самом деле, есть решение, только если 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)
с k > 0
, уравнение становится:
ax + by = k*gcd(a, b) (1)
(a / k)x + (b / k)y = gcd(a, b) (2)
Так что просто найдите решение для (2) или, альтернативно, найдите решение для (1) и умножьте x
и y
на k
.