Получение всех решений. Нахождения количества решений или самих решений в заданном отрезке

Получение всех решений

Покажем, как получить все остальные решения (а их бесконечное множество) диофантова уравнения, зная одно из решений (x_0,y_0).

Заметим, что, прибавив к x_0 число b/g и одновременно отняв a/g от y_0, мы не нарушим равенства:

a * (x_0 + b/g) + b * (y_0 - a/g) = a * x_0 + b * y_0 + a * b / g - a * b / g = c

Очевидно, что этот процесс можно повторять сколько угодно, т.е. все числа вида:

x = x_0 + k * b/g, y = y_0 - k * a/g, k - целое, являются решениями диофантова уравнения.

Более того, только числа такого вида и являются решениями, т. е. мы описали множество всех решений диофантова уравнения (оно получилось бесконечным, если не наложено дополнительных условий).

Нахождения количества решений или самих решений в заданном отрезке

Пусть даны два отрезка [min_x; max_x] и [min_y; max_y], и требуется найти количество решений (x, y) диофантова уравнения, лежащих в данных отрезках соответственно. Заметим, что если одно из чисел a, b равно нулю, то задача имеет не больше одного решения, поэтому эти случаи мы в данном разделе исключаем из рассмотрения.

Сначала найдём решение с минимальным подходящим x, т. е. x >= min_x. Для этого сначала найдём любое решение диофантова уравнения. Затем получим из него решение с наименьшим x >= min_x — для этого воспользуемся процедурой, описанной в предыдущем пункте, и будем уменьшать/увеличивать x, пока оно не окажется >= min_x, и при этом минимальным. Это можно сделать за O(1), посчитав, с каким коэффициентом нужно применить это преобразование, чтобы получить минимальное число, большее либо равное min_x. Обозначим найденный x через Lx1. Аналогичным образом можно найти и решение с максимальным подходящим x = Rx1, т. е. x <= max_x.

Далее перейдём к удовлетворению ограничений на y, т. е. к рассмотрению отрезка [min_y; max_y]. Способом, описанным выше, найдём решение с минимальным y >= min_y, а также решение с максимальным y <= max_y. Обозначим x-коэффициенты этих решений через Lx2 и Rx2 соответственно.

Пересечём отрезки [Lx1; Rx1] и [Lx2; Rx2]; обозначим получившийся отрезок через [Lx; Rx]. Утверждается, что любое решение, у которого x-коэффициент лежит в [Lx; Rx] — любое такое решение является подходящим. Это верно в силу построения этого отрезка: сначала мы отдельно удовлетворили ограничения на x и y, получив два отрезка, а затем пересекли их, получив область, в которой удовлетворяются оба условия. Таким образом, количество решений будет равняться длине этого отрезка, делённой на |b| (поскольку x-коэффициент может изменяться только на +- b), и плюс один.

Код решения приводиться не будет, так как он требует учёта множества частных случаев (в том числе случаев, когда a, b могут быть меньше нуля).