1. Идея

Нужно найти число x, для которого выполняется сравнение a * x ≡ 1 (mod m).

Такое число называется обратным к a по модулю m.

Ключевой факт из теории чисел: обратный элемент существует тогда и только тогда, когда gcd(a, m) = 1.

Чтобы не просто проверить существование, а сразу найти x, удобно использовать расширенный алгоритм Евклида. Он позволяет представить наибольший общий делитель в виде:

a * s + m * t = gcd(a, m)

Если gcd(a, m) = 1, то получаем:

a * s + m * t = 1

Если посмотреть на это равенство по модулю m, то слагаемое m * t исчезает, и остаётся:

a * s ≡ 1 (mod m)

Значит, s и есть искомый обратный элемент. Нужно только привести его к диапазону от 0 до m - 1, а по условию ответ должен лежать в [1, m - 1].

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

1. Если gcd(a, m) != 1, то обратного элемента не существует, и нужно вывести -1.

2. Если gcd(a, m) = 1, то расширенный алгоритм Евклида находит коэффициенты s и t, такие что: a * s + m * t = 1.

3. Тогда число s может быть отрицательным или слишком большим, поэтому его нужно нормализовать: x = (s % m + m) % m

   В Python достаточно x = s % m, потому что остаток там уже неотрицательный.

4. При 1 <= a < m и m >= 2 значение x = 0 не получится, если обратный элемент существует. Действительно, a * 0 ≡ 0, а не 1.

3. Алгоритм

Будем использовать итеративную версию расширенного алгоритма Евклида.

Поддерживаем значения:

• old_r, r — текущие остатки,
• old_s, s — коэффициенты при a,
• old_t, t — коэффициенты при m.

Изначально:

• old_r = a, r = m
• old_s = 1, s = 0
• old_t = 0, t = 1

Пока r != 0:

1. Находим q = old_r / r.
2. Делаем шаг алгоритма Евклида:
   • обновляем остатки,
   • обновляем коэффициенты.

После завершения:

• old_r — это gcd(a, m),
• old_s и old_t — коэффициенты из равенства a * old_s + m * old_t = old_r.

Дальше:

• если old_r != 1, выводим -1;
• иначе ответ — это old_s, приведённый по модулю m.

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

Расширенный алгоритм Евклида устроен так, что на каждом шаге сохраняется представление текущих остатков через a и m.

То есть для текущих значений всегда верно:

• old_r = a * old_s + m * old_t
• r = a * s + m * t

Когда алгоритм заканчивается, r = 0, а old_r равен gcd(a, m). Значит, мы получаем:

a * old_s + m * old_t = gcd(a, m)

Теперь рассмотрим два случая.

Случай 1: gcd(a, m) != 1

Тогда равенство имеет вид:

a * old_s + m * old_t = d, где d != 1

Получить сравнение a * x ≡ 1 (mod m) невозможно, значит обратного элемента нет.

Случай 2: gcd(a, m) = 1

Тогда:

a * old_s + m * old_t = 1

Перенесём m * old_t вправо по модулю m. Поскольку любое число вида m * k сравнимо с нулём по модулю m, получаем:

a * old_s ≡ 1 (mod m)

Значит, old_s — обратный элемент к a по модулю m.

Если old_s отрицателен, это не проблема: числа, отличающиеся на кратное m, задают один и тот же остаток. Поэтому нормализация через % m даёт правильный ответ в диапазоне [0, m - 1], а при существовании обратного элемента это будет число из [1, m - 1].

5. Сложность

Расширенный алгоритм Евклида работает за O(log m).

Используемая дополнительная память — O(1).

6. Код на C++17

#include <iostream>

using namespace std;

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

    long long old_r = a, r = m;
    long long old_s = 1, s = 0;
    long long old_t = 0, t = 1;

    while (r != 0) {
        long long q = old_r / r;

        long long new_r = old_r - q * r;
        old_r = r;
        r = new_r;

        long long new_s = old_s - q * s;
        old_s = s;
        s = new_s;

        long long new_t = old_t - q * t;
        old_t = t;
        t = new_t;
    }

    if (old_r != 1) {
        cout << -1 << '\n';
        return 0;
    }

    long long x = ((old_s % m) + m) % m;
    cout << x << '\n';
    return 0;
}

7. Код на Python 3

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

old_r, r = a, m
old_s, s = 1, 0
old_t, t = 0, 1

while r != 0:
    q = old_r // r

    old_r, r = r, old_r - q * r
    old_s, s = s, old_s - q * s
    old_t, t = t, old_t - q * t

if old_r != 1:
    print(-1)
else:
    x = old_s % m
    print(x)