Диофантово уравнение II порядка

Диофантово уравнение II порядка

       Диофантово уравнение второго порядка имеет вид:

a * x + b * y = c; a, b, c - известные, x, y - неизвестные

 

       Замечу, что зачастую нужно найти не просто какое-то решение, а:

● все решения

● количество решений или сами решения в определённом отрезке

● нахождение решений с наименьшей суммой неизвестных

 

Вырожденный случай

Один вырожденный случай мы сразу исключим из рассмотрения: когда a = b = 0. В этом случае, понятно, уравнение имеет либо бесконечно много произвольных решений, либо же не имеет решений вовсе (в зависимости от того, c = 0 или нет).

 

Нахождение одного решения

 

Найти одно из решений диофантова уравнения с двумя неизвестными можно с помощью Расширенного алгоритма Евклида. Предположим сначала, что числа a и b неотрицательны.

 

Расширенный алгоритм Евклида по заданным неотрицательным числам a и b находит их наибольший общий делитель g, а также такие коэффициенты x_g и y_g, что:

a * x_g + b * y_g = g.

 

Утверждается, что если c делится на g = gcd(a,b), то диофантово уравнение a * x + b * y = c имеет решение; в противном случае диофантово уравнение решений не имеет. Доказательство следует из очевидного факта, что линейная комбинация двух чисел по-прежнему должна делиться на их общий делитель.

 

Предположим, что c делится на g, тогда, очевидно, выполняется:

a * x_g * (c / g) + b * y_g * (c / g) = c

 

т. е. одним из решений диофантова уравнения являются числа:

x_0 = x_g * (c / g), y_0 = y_g

 

Мы описали решение в случае, когда числа a и b неотрицательны. Если же одно из них или они оба отрицательны, то можно поступить таким образом: взять их по модулю (абсолютное значение, а не модулярная арифметика) и применить к ним алгоритм Евклида, как было описано выше, а затем изменить знак найденных x_0 и y_0 в соответствии с настоящим знаком чисел a и b соответственно.

 

Реализация (напомним, здесь мы считаем, что входные данные a=b=0 недопустимы):

 

bool find_any_solution(int a, int b, int c, int & x0, int & y0, int & g) {        g = gcdex(abs(a), abs(b), x0, y0);        if (c % g!= 0)                    return false;        x0 *= c / g;        y0 *= c / g;        if (a < 0) x0 *= -1;        if (b < 0) y0 *= -1;        return true; }