Линейные диофантовы уравнения с двумя переменными - Уравнения - Математика - Каталог статей - AlexLat
Главная » Статьи » Математика » Уравнения

Линейные диофантовы уравнения с двумя переменными

Линейные диофантовы уравнения с двумя переменными

Диофантово уравнение с двумя неизвестными имеет вид:


α • x+b • y= c,

где α ,b,c  — заданные целые числа,x и    — неизвестные целые числа.

Ниже рассматриваются несколько классических задач на эти уравнения: нахождение любого 

решения, получение всех решений, нахождение количества решений и сами решения в 

определённом отрезке, 

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

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

Один вырожденный случай мы сразу исключим из рассмотрения: когда α = b = 0  . 

 В этом случае, 

понятно, уравнение имеет либо бесконечно много произвольных решений, либо же не 

имеет решений 

вовсе (в зависимости от того,  c = 0 или нет).

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

Найти одно из решений диофантова уравнения с двумя неизвестными можно с помощью

 Расширенного 

алгоритма Евклида. Предположим сначала, что числа α  и  b неотрицательны.

Расширенный алгоритм Евклида по заданным неотрицательным числам α  и b 

находит их наибольший 

общий делитель  g, а также такие коэффициенты xg  и yg , что:

α•xg+b•yg = g

Утверждается, что если  c  cделится на g = gcd(α,b) , то диофантово уравнение  

 α • x +b • y = c

имеет решение; в противном случае диофантово уравнение решений не имеет. 

Доказательство следует из очевидного факта, что линейная комбинация двух чисел

 по-прежнему должна делиться на их общий делитель.

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

α•xg•(c/g)+b• yg•(c/g) = c,

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


Мы описали решение в случае, когда числа α   и b  неотрицательны. 

Если же одно из них или они оба отрицательны, то можно поступить таким образом:

взять их по модулю и применить к ним алгоритм  

Евклида, как было описано выше, а затем изменить знак найденных x0  и y0  

в соответствии с 

настоящим знаком чисел  α и  соответственно.

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

недопустимы):

int gcd (int a, int b, int & x, int & y) {
 if (a == 0) {
 x = 0; y = 1;
 return b;
 }
 int x1, y1;
 int d = gcd (b%a, a, x1, y1);
 x = y1 - (b / a) * x1;
 y = x1;
 return d;
}
 
bool find_any_solution (int a, int b, int c, int & x0, int & y0, int & g) 
{g = gcd (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;
}

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

Покажем, как получить все остальные решения (α и х бесконечное множество) 

диофантова 

уравнения, зная одно из решений (x0,y0) .

Итак, пусть g = gcd(α,b)  , а числа x0,y0  удовлетворяют условию:

α•x0+b•y0 = c

Тогда заметим, что, прибавив к x0 число b/g  и одновременно отняв α/g  от y0 , 

мы не нарушим равенства:

α•(x0+b/g)+b•(y0-α/g)=α•x0+b•y0+α•b/g-b•α/g=c

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

вида:



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

Более того, только числа такого вида и являются решениями, т.е. мы описали 

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

 если не наложено дополнительных условий).

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

Пусть даны два отрезка[minx;maxx]и[miny;maxy]   , и требуется найти количество 

решений (x,y)  диофантова уравнения, лежащих в данных отрезках соответственно.

Заметим, что если одно из чисел α,b  равно нулю, то задача имеет не больше одного 

решения, поэтому 

эти случаи мы в данном разделе исключаем из рассмотрения.

Сначала найдём решение с минимальным подходящим  x, т.еxminx.x≥ minx . 

Для этого сначала найдём любое решение диофантова уравнения (см. пункт 1). 

Затем получим из него решение с наименьшим .x≥ minx — для этого воспользуемся 

процедурой, описанной в предыдущем пункте, и будем уменьшать/увеличивать x,

 пока оно не окажется ≥ minx, и при этом минимальным. Это можно сделать за O(1),

посчитав, с каким коэффициентом нужно применить это преобразование, чтобы получить

 минимальное число, большее либо равное minx. Обозначим найденный xчерез lx1 .

Аналогичным образом можно найти и решение с максимальным подходящим x = rx1,= , 

т.е. x ≤ maxx.

Далее перейдём к удовлетворению ограничений на y, т.е. к рассмотрению отрезка

[ miny;maxy;] . 

Способом, описанным выше, найдём решение с минимальным y≥miny , а также

 решение с максимальным ymaxy. Обозначим x-коэффициенты этих решений 

через lx2; и rx2   соответственно.

Пересечём отрезки [lx1;и rx1]   ; обозначим получившийся отрезок через [lx;rx] 

Утверждается, что любое решение, у которого x-коэффициент лежит в [lx;rx] — любое 

такое решение является подходящим. (Это верно в силу построения этого отрезка: 

сначала мы отдельно удовлетворили ограничения на x и y, получив два отрезка, 

а затем пересекли их, получив область, в которой удовлетворяются оба условия.)

Таким образом, количество решений будет равняться длине этого отрезка, делённой 

на  |b|(поскольку x-коэффициент может изменяться только на ±b ), и плюс один.

Приведём реализацию (она получилась достаточно сложной, поскольку требуется 

 аккуратно рассматривать случаи положительных и отрицательных коэффициентов 

α и b):

void shift_solution (int & x, int & y, int a, int b, int cnt) {
 x += cnt * b;
 y -= cnt * a;
}
 
int find_all_solutions (int a, int b, int c, int minx, int maxx, int miny, int maxy) 
{int x, y, g;
 if (! find_any_solution (a, b, c, x, y, g))
 return 0;
 a /= g; b /= g;
 
 int sign_a = a>0 ? +1 : -1;
 int sign_b = b>0 ? +1 : -1;
 
 shift_solution (x, y, a, b, (minx - x) / b);
 if (x < minx)
 shift_solution (x, y, a, b, sign_b);
 if (x > maxx)
 return 0;
 int lx1 = x;
 
 shift_solution (x, y, a, b, (maxx - x) / b);
 if (x > maxx)
 shift_solution (x, y, a, b, -sign_b);
 int rx1 = x;
 
 shift_solution (x, y, a, b, - (miny - y) / a);
 if (y < miny)
 shift_solution (x, y, a, b, -sign_a);
 if (y > maxy)
 return 0;
 int lx2 = x;
 
 shift_solution (x, y, a, b, - (maxy - y) / a);
 if (y > maxy)
 shift_solution (x, y, a, b, sign_a);
 int rx2 = x;
 
 if (lx2 > rx2)
 swap (lx2, rx2);
 int lx = max (lx1, lx2);
 int rx = min (rx1, rx2);
 
 return (rx - lx) / abs(b) + 1;
}

Также нетрудно добавить к этой реализации вывод всех найденных решений: 

для этого достаточно перебрать x в отрезке  [lx;rx]с шагом|b|, найдя для каждого 

из них соответствующий y непосредственно из уравнения αx+by = c.

Нахождение решения в заданном отрезке с наименьшей суммой x+y

Здесь на x и на y также должны быть наложены какие-либо ограничения, 

иначе ответом 

практически всегда будет минус бесконечность.

Идея решения такая же, как и в предыдущем пункте: сначала находим любое

 решение  диофантова уравнения, а затем, применяя описанную в предыдущем 

 пункте процедуру, придём к наилучшему решению.

Действительно, мы имеем право выполнить следующее преобразование 

(см. предыдущий пункт):

Заметим, что при этом сумма x+y  меняется следующим образом:

x’+y’= x+y+k•(b/g - α/9) = x+y+k• (b-a)/g 


Т.е. если α <b, то нужно выбрать как можно меньшее значение k, если α >b,

 то нужно  выбрать как можно большее значение k .

Если α = b, то мы никак не сможем улучшить решение, — все решения будут 

обладать одной и той же суммой.

Категория: Уравнения | Добавил: alexlat (26.06.2012)
Просмотров: 914 | Рейтинг: 0.0/0
Всего комментариев: 0
Добавлять комментарии могут только зарегистрированные пользователи.
[ Регистрация | Вход ]