добавлено: 10 Jun 2008 18:15 Линейные диофантовы уравнения с двумя переменнымиДиофантово уравнение с двумя неизвестными имеет вид: где Ниже рассматриваются несколько классических задач на эти уравнения: нахождение любого решения, получение всех решений, нахождение количества решений и сами решения в определённом отрезке, нахождение решения с наименьшей суммой неизвестных. Вырожденный случайОдин вырожденный случай мы сразу исключим из рассмотрения: когда Нахождение одного решенияНайти одно из решений диофантова уравнения с двумя неизвестными можно с помощью Расширенного алгоритма Евклида. Предположим сначала, что числа Расширенный алгоритм Евклида по заданным неотрицательным числам Утверждается, что если Предположим, что т.е. одним из решений диофантова уравнения являются числа: Мы описали решение в случае, когда числа Реализация (напомним, здесь мы считаем, что входные данные 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; } Получение всех решенийПокажем, как получить все остальные решения (а их бесконечное множество) диофантова уравнения, зная одно из решений Итак, пусть Тогда заметим, что, прибавив к Очевидно, что этот процесс можно повторять сколько угодно, т.е. все числа вида: являются решениями диофантова уравнения. Более того, только числа такого вида и являются решениями, т.е. мы описали множество всех решений диофантова уравнения (оно получилось бесконечным, если не наложено дополнительных условий). Нахождение количества решений и сами решения в заданном отрезкеПусть даны два отрезка Заметим, что если одно из чисел Сначала найдём решение с минимальным подходящим Аналогичным образом можно найти и решение с максимальным подходящим Далее перейдём к удовлетворению ограничений на Пересечём отрезки Таким образом, количество решений будет равняться длине этого отрезка, делённой на Приведём реализацию (она получилась достаточно сложной, поскольку требуется аккуратно рассматривать случаи положительных и отрицательных коэффициентов 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+yЗдесь на Идея решения такая же, как и в предыдущем пункте: сначала находим любое решение диофантова уравнения, а затем, применяя описанную в предыдущем пункте процедуру, придём к наилучшему решению. Действительно, мы имеем право выполнить следующее преобразование (см. предыдущий пункт): Заметим, что при этом сумма Т.е. если Если Задачи в online judgesСписок задач, которые можно сдать на тему диофантовых уравнений с двумя неизвестными:
|