Есть ли способ решить в целых числах уравнение вида ax+by+cz = d?

Question

[Atmosfiren]

Можно ли уравнение вида: ax+by+cz = d решить в целых числах каким-то известным способом? Рассматривается случай, когда решение точно есть. Все коэффициенты - целые. Переменных может быть и больше 3 (до 10).

Answer 1

[Wataru]

Для двух переменных задача решается через расширенный алгоритм Евклида.

Решайте итеративно, добавляя новые переменные. Вот вы получили первые k переменных так что их сумма с коэффициентами равна GCD() коэффициентов. Пусть этот gcd(a1,a2,... ak) = d. Теперь решите тем же алгоритмом уравнение d*x + a(k+1)y = gcd(d,a(k+1)). y будет искомым значением последней переменной, а все предыдущие значения надо домножить на значение x.

В конце вы нашли GCD всех коэффициентов и вы можете проверить, что правая часть на него делится. если нет - решения нет. Если делится, то надо на результат деления домножить все переменные.

Да, тут еще спецэффект есть, что с отрицательными числами не работает GCD. Надо поменять знаки у коэффициентов, запомнить это и в конце поменять знаки у переменных назад.

Решение за O(n log M), где n - количество переменных, M - максимальное значение коэффициентов.

Answer 2

[milssky]

Что-то мне думается, что как-то так или так