1. Идея

Нужно найти такие целые числа x и y, чтобы

a * x + b * y = gcd(a, b).

Это классическая задача на расширенный алгоритм Евклида. Обычный алгоритм Евклида находит только значение gcd(a, b), а расширенный — ещё и коэффициенты Безу x и y.

Главная идея такая:

• если уже известно решение для пары (b, a % b),
• то из него можно восстановить решение для пары (a, b).

Именно на этом построена рекурсия.

2. Наблюдения

Наблюдение 1. Базовый случай

Если b = 0, то

gcd(a, 0) = a.

Тогда равенство

a * x + 0 * y = a

выполняется, например, при x = 1, y = 0.

То есть в базовом случае ответ сразу известен:

• g = a
• x = 1
• y = 0

Наблюдение 2. Переход к меньшей задаче

Если b != 0, запускаем алгоритм для чисел:

• b
• a % b

Пусть для них уже найдены числа x1 и y1, такие что

b * x1 + (a % b) * y1 = g.

Но

a % b = a - (a / b) * b

где деление целочисленное.

Подставим это в равенство:

b * x1 + (a - (a / b) * b) * y1 = g

Раскроем скобки:

a * y1 + b * (x1 - (a / b) * y1) = g

Значит, для исходной пары (a, b) подходят:

• x = y1
• y = x1 - (a / b) * y1

Это и есть формула восстановления ответа после рекурсивного вызова.

Наблюдение 3. Почему числа не выходят за ограничения

По условию a, b <= 10^9. Для таких значений коэффициенты Безу, найденные расширенным алгоритмом Евклида, спокойно помещаются в тип long long и в Python int. Ограничение |x|, |y| <= 10^18 также выполняется.

3. Алгоритм

Опишем рекурсивную функцию extended_gcd(a, b).

Она возвращает три числа:

• g = gcd(a, b)
• x
• y

такие, что

a * x + b * y = g.

Шаги алгоритма

1. Если b == 0, вернуть:

   • g = a
   • x = 1
   • y = 0

2. Иначе рекурсивно решить задачу для (b, a % b):

   • получить g, x1, y1

3. Восстановить коэффициенты для (a, b):

   • x = y1
   • y = x1 - (a / b) * y1

4. Вывести g x y.

4. Почему это работает

Докажем корректность алгоритма.

База рекурсии

При b = 0 функция возвращает:

• g = a
• x = 1
• y = 0

Проверим равенство:

a * 1 + 0 * 0 = a

А так как gcd(a, 0) = a, всё верно.

Переход

Предположим, что рекурсивный вызов для (b, a % b) работает правильно. То есть он возвращает g, x1, y1, для которых

b * x1 + (a % b) * y1 = g

и g = gcd(b, a % b).

Из свойства алгоритма Евклида известно, что

gcd(a, b) = gcd(b, a % b),

значит это действительно нужный НОД.

Теперь выразим остаток:

a % b = a - (a / b) * b

Подставим:

b * x1 + (a - (a / b) * b) * y1 = g

После перегруппировки получаем:

a * y1 + b * (x1 - (a / b) * y1) = g

Значит, если взять

• x = y1
• y = x1 - (a / b) * y1

то выполнится

a * x + b * y = g.

Следовательно, функция корректно восстанавливает ответ для (a, b).

Так как на каждом шаге второй аргумент строго уменьшается по алгоритму Евклида, рекурсия обязательно дойдёт до случая b = 0.

Значит, алгоритм всегда завершится и вернёт правильные g, x, y.

5. Сложность

Алгоритм делает столько же шагов, сколько обычный алгоритм Евклида.

• Время: O(log(min(a, b)))
• Память:
  • O(log(min(a, b))) из-за рекурсии

6. Код на C++17

#include <iostream>
using namespace std;

long long extended_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 = extended_gcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return g;
}

int main() {
    long long a, b;
    cin >> a >> b;

    long long x, y;
    long long g = extended_gcd(a, b, x, y);

    cout << g << " " << x << " " << y << "\n";
    return 0;
}

7. Код на Python 3

a, b = map(int, input().split())

def extended_gcd(a, b):
    if b == 0:
        return a, 1, 0
    g, x1, y1 = extended_gcd(b, a % b)
    x = y1
    y = x1 - (a // b) * y1
    return g, x, y

g, x, y = extended_gcd(a, b)
print(g, x, y)