Расширенный алгоритм Евклида
Соотношение Безу утверждает, что существуют целые , такие что
Расширенный алгоритм Евклида находит НОД вместе с этими коэффициентами. Коэффициенты могут быть отрицательными, даже когда неотрицательны.
Если , выбираем и . Тогда .
Иначе рекурсивно решаем задачу для пары . Пусть вызов вернул , удовлетворяющие
Пусть . Подставив , получаем
Следовательно, коэффициенты для равны
База и это рекуррентное соотношение строят коэффициенты Безу, что доказывает соотношение.
Обратный элемент по модулю — это значение , удовлетворяющее
Обратный элемент существует ровно тогда, когда .
Если обратный элемент существует, то для некоторого целого . Любой общий делитель должен делить , поэтому их НОД равен .
Обратно, когда НОД равен , расширенный алгоритм Евклида находит . Взяв это равенство по модулю , видим, что его коэффициент — обратный элемент. Приводим его к диапазону .
Линейное диофантово уравнение — это задача поиска целочисленных решений уравнения
Сначала разберём случай : если , решением является любая пара, иначе решений нет.
В остальных случаях пусть . Решение существует ровно тогда, когда .
Необходимость следует из того, что делит оба слагаемых в левой части. Для достаточности возьмём коэффициенты Безу и умножим их на . Это даёт одно решение .
Все решения имеют вид
Подстановка показывает, что каждая такая пара подходит. Чтобы доказать, что других решений при нет, вычтем уравнения для двух решений:
Так как и взаимно просты, делит . Запишем ; отсюда обязательно .
Если ровно один коэффициент равен нулю, другой фиксирует одну переменную, а вторая остаётся произвольной. Та же формула описывает и эти решения.
Функция возвращает НОД и записывает коэффициенты Безу в по ссылкам. Для указанного диапазона входных данных эти коэффициенты и промежуточные значения рекуррентных обновлений помещаются в .
Функция требует и возвращает обратный элемент из или , если его не существует.
Функция принимает любое знаковое 64-битное . Она возвращает, существует ли решение, и в случае успеха записывает одно решение в . При умножении можно выйти за пределы , поэтому эта функция использует — знаковый 128-битный целый тип GNU C++17.
Расширенный алгоритм Евклида проходит те же шаги с остатками, что и алгоритм Евклида. Он занимает времени и столько же памяти на стек рекурсии. Поиск одного решения уравнения имеет ту же оценку. Вычисление обратного элемента по модулю занимает времени и памяти на стек.
#include <bits/stdc++.h>
using namespace std;
using i128 = __int128_t;
long long ext_gcd(long long a, long long b, long long &x, long long &y) {
if (b == 0) {
x = 1;
y = 0;
return a;
}
long long x1, y1;
long long g = ext_gcd(b, a % b, x1, y1);
x = y1;
y = x1 - (a / b) * y1;
return g;
}
long long inverse(long long a, long long m) {
long long x, y;
if (ext_gcd(a % m, m, x, y) != 1) {
return -1;
}
x %= m;
if (x < 0) {
x += m;
}
return x;
}
bool find_solution(long long a, long long b, long long c, i128 &x, i128 &y) {
if (a == 0 && b == 0) {
x = y = 0;
return c == 0;
}
long long x0, y0;
long long g = ext_gcd(a, b, x0, y0);
if (c % g != 0) {
return false;
}
i128 k = (i128)c / g;
x = (i128)x0 * k;
y = (i128)y0 * k;
return true;
}