Возможно, вы всё ещё используете малую теорему Ферма, чтобы находить обратные элементы по модулю простого числа $$$p$$$.

Если p — простое число и x не делится на p, то по малой теореме Ферма:

Следовательно,

Поэтому стандартный способ найти обратный элемент — использовать бинарное возведение в степень:

int binpow(int a, int n) {
    int res = 1;
    while (n) {
        if (n&1) res = 1LL * res * a % mod;
        a = 1LL * a * a % mod;
        n >>= 1;
    }
    return res;
}
int inv(int x) {
    return binpow(x, mod - 2);
}

Этот способ отлично работает. Но для такой частой операции хочется иметь что-то короче.

Например, обратный элемент можно записать так:

int inv(int x) {
    return x == 1 ? 1 : mod - 1LL * (mod / x) * inv(mod % x) % mod;
}

Теперь докажем, почему эта формула работает.

Сначала запишем mod через деление с остатком:

Следовательно,

Так как мы работаем по модулю mod, значение mod сравнимо с 0, поэтому:

Теперь умножим обе части на $$$inv(mod\%x)$$$ $$$\big ($$$ мы знаем, что $$$(mod \% x) * inv(mod \% x) \equiv 1 \pmod{mod}\big)$$$:

Так как mod — простое число и x не делится на mod, то деление на x корректно по модулю mod.

Разделив обе части на x, получаем:

Но $$$x^{-1}$$$ — это обратный элемент к x, поэтому:

Конечно, мы хотим получить неотрицательное значение, поэтому вместо того, чтобы возвращать отрицательное число напрямую, добавим mod:

Так мы получили рекурсивную формулу:

int inv(int x) {
    return x == 1 ? 1 : mod - 1LL * (mod / x) * inv(mod % x) % mod;
}

Рекурсия останавливается при x = 1, потому что inv(1) = 1.

Сложность — $$$O(\log mod)$$$, как и в первом решении, но реализация получается гораздо короче, чем бинарное возведение в степень.