Maybe you are still using Fermat's Little Theorem to find inverses modulo a prime numberВозможно, вы всё ещё используете малую теорему Ферма, чтобы находить обратные элементы по модулю простого числа $p$.↵
==================↵
↵
IfЕсли `p` is prime and `x` is not divisible by `p`, then by Fermat's Little Theorem: — простое число и `x` не делится на `p`, то по малой теореме Ферма:↵
↵
$$x^{p-1}\equiv 1\pmod p$$↵
↵
Therefore, Следовательно,↵
↵
$$x^{p-2}\equiv x^{-1}\pmod p$$↵
↵
So the usual way to find the modular inverse is to use binary exponentiationПоэтому стандартный способ найти обратный элемент — использовать бинарное возведение в степень:↵
↵
~~~~~↵
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);↵
}↵
~~~~~↵
This works perfectly fine. But for such a common operation, it is nice to have something shorter.↵
==================↵
↵
For example, we can write the modular inverse like this↵
Этот способ отлично работает. Но для такой частой операции хочется иметь что-то короче.↵
==================↵
↵
Например, обратный элемент можно записать так:↵
↵
~~~~~↵
int inv(int x) {↵
return x == 1 ? 1 : mod - 1LL * (mod / x) * inv(mod % x) % mod;↵
}↵
~~~~~↵
↵
Now let's prove why this formula works.↵
↵
First, write `mod` using division with remainderТеперь докажем, почему эта формула работает.↵
↵
Сначала запишем `mod` через деление с остатком:↵
↵
$$mod = (mod / x) * x + mod \% x$$↵
↵
ThereforeСледовательно,↵
↵
$$mod \% x = mod - (mod / x) * x$$↵
↵
Since we are working modulo `mod`, the value `mod` is congruent to `0`, soТак как мы работаем по модулю `mod`, значение `mod` сравнимо с `0`, поэтому:↵
↵
$$mod \% x\equiv -(mod/x) * x \pmod{mod}$$↵
↵
Now multiply both sides byТеперь умножим обе части на $inv(mod\%x)$ $\big($ We know thatмы знаем, что $(mod \% x) * inv(mod \% x) \equiv 1 \pmod{mod}\big)$:↵
↵
$$1\equiv -(mod / x) * x * inv(mod \% x) \pmod{mod}$$↵
↵
Since `mod` is prime and `x` is not divisible by `mod`, division by `x` is valid modulo `mod`.↵
↵
Dividing both sides by `x`, we getТак как `mod` — простое число и `x` не делится на `mod`, то деление на `x` корректно по модулю `mod`.↵
↵
Разделив обе части на `x`, получаем:↵
↵
$$x^{-1} \equiv -(mod / x) * inv(mod \% x) \pmod{mod}$$↵
↵
ButНо $x^{-1}$ is exactly the modular inverse of `x`, so this gives us— это обратный элемент к `x`, поэтому:↵
↵
$$inv(x) \equiv -(mod / x) * inv(mod \% x) \pmod{mod}$$↵
↵
Of course we want a non-negative value, so instead of returning the negative number directly, we addКонечно, мы хотим получить неотрицательное значение, поэтому вместо того, чтобы возвращать отрицательное число напрямую, добавим `mod`: ↵
↵
$$inv(x) \equiv mod - (mod / x) * inv(mod \% x) \pmod{mod}$$↵
↵
So we have derived the recursive formulaТак мы получили рекурсивную формулу:↵
↵
~~~~~↵
int inv(int x) {↵
return x == 1 ? 1 : mod - 1LL * (mod / x) * inv(mod % x) % mod;↵
}↵
~~~~~↵
↵
The recursion stops at `x = 1` becauseРекурсия останавливается при `x = 1`, потому что `inv(1) = 1`.↵
↵
The complexity is $O(\log mod)$, similar to the first solution, but the implementation is much shorter than binary exponentiationСложность — $O(\log mod)$, как и в первом решении, но реализация получается гораздо короче, чем бинарное возведение в степень.
