@Atmosfiren

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

Можно ли уравнение вида: ax+by+cz = d решить в целых числах каким-то известным способом? Рассматривается случай, когда решение точно есть. Все коэффициенты - целые. Переменных может быть и больше 3 (до 10).
  • Вопрос задан
  • 144 просмотра
Решения вопроса 2
milssky
@milssky
Координатор племени фиолетовых обезьянок
Что-то мне думается, что как-то так или так
Ответ написан
wataru
@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 - максимальное значение коэффициентов.
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы