Task 82. Уравнение
UniLecsЗадача: дано математическое уравнение a*x + b*y = 1.
Необходимо найти только целочиселнные решения этого уравнения и такие, что x >= 0.
Входные данные: a, b, где 0 <= a, b <= 10^9
Вывод: минимально возможное неотрицательное значение x и соот-е для него целое значение y. Если решения нет, вывести соот-е сообщение.
Пример:
1. a = 7, b = 11,
Answer: 8 -5
2. a = 5, b = 3
Answer: 2 -3
Идея:
Первый шаг: воспользуемся расширенным алгоритмом Евклида, по заданным a,b найдем такие d = НОД(a, b), x0, y0, что a*x0 + b*y0 = d.
Т.к. мы решаем уравнение a*x + b*y = 1, то при d > 1 решений не будет.
Все решения уравнения a*x + b*y = 1 находятся по формуле:
где (x0, y0) - частичное решение исходного уравнения.
Второй шаг: для того, чтобы x было минимально возможным неотрицательным значением, нужно чтобы k было наименьшим, для ктр x0 + k*b >= 0. Или k >= -x0 / b.
Наименьшим целым k, ктр удовлетворяет последнему неравенству, будет k = Math.Celling(-x0 / b). Для этого значения k и нужно найти решение.
Шаг третий: т.к. расширенный алгоритм Евклида находит такое решение (x0, y0), для ктр (Abs(x0) + Abs(y0)) минимальна, то при x0 > 0 искомое решение (с наименьшим неотрицательным значением x) равно:
Если в частичном решении (x0, y0) выполняется неравенство x0 >= 0, то оно само и будет решением задачи.
Рассмотрим пример: a = 7, b = 11. Применим расширенный алгоритм Евклида, получим частичное решение x0 = -3, y0 = 2. После получим k = Math.Celling(- (-3) / 11) = 1. Тогда наше решение будет
x = -3 + 1*11 = 8
y = 2 - 1*7 = -5
Реализация:
https://gist.github.com/unilecs/9dcc9274ebbfa347298241e8bd05a97a
Тест: