Балансировка магических кристаллов — разбор

1. Идея

Нужно не просто найти g = gcd(a, b), но и подобрать такие целые x и y, чтобы выполнялось:

a * x + b * y = g

Это классическая задача на расширенный алгоритм Евклида.

Обычный алгоритм Евклида умеет находить НОД двух чисел. Расширенный алгоритм Евклида делает больше: одновременно с НОД он находит коэффициенты x и y из равенства Безу.

Именно это и требуется в задаче.

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

Наблюдение 1. НОД можно выразить через a и b

Для любых целых a и b существуют такие целые x и y, что:

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

Это стандартный факт из теории чисел.

Наблюдение 2. База рекурсии очевидна

Если b = 0, то:

• gcd(a, 0) = a
• равенство можно записать так:

a * 1 + 0 * 0 = a

Значит, в этом случае подходит:

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

Наблюдение 3. Переход строится из шага алгоритма Евклида

Если мы уже умеем находить коэффициенты для пары (b, a % b), то можно восстановить коэффициенты для пары (a, b).

Пусть для чисел b и a % b уже найдено:

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. Алгоритм

Будем реализовывать рекурсивную функцию extended_gcd(a, b).

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

• g — НОД чисел 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.

5. В основной программе:

   • считываем a и b
   • вызываем extended_gcd(a, b)
   • выводим g x y

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

Докажем корректность по рекурсии.

База

Если b = 0, функция возвращает g = a, x = 1, y = 0.

Проверим:

a * x + b * y = a * 1 + 0 * 0 = a = gcd(a, 0)

Значит, база корректна.

Переход

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

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

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

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

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

Значит, g действительно равен gcd(a, 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

То есть функция действительно возвращает корректные коэффициенты.

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

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)