Какой алгоритм используется для решения линейного диофантова уравнения: ax + by = c - PullRequest
1 голос
/ 07 февраля 2011

Я ищу решение целых чисел здесь.Я знаю, что оно имеет бесконечно много решений, полученных из решения первой пары и gcd (a, b) | c.Однако как мы можем найти первую пару решений?Есть ли алгоритм для решения этой проблемы?

Спасибо,
Чан

1 Ответ

9 голосов
/ 07 февраля 2011

Обратите внимание, что не всегда есть решение.На самом деле, есть решение, только если 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.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...