Обратный по любому модулю в 2 строчки: различия между версиями
Материал из Algocode wiki
(Новая страница: «==Обратный по любому модулю в 2 строчки== ===Реализация=== Сначала приведем реализацию, а по...») |
|||
| Строка 5: | Строка 5: | ||
Сначала приведем реализацию, а потом уже поймем, почему она работает: | Сначала приведем реализацию, а потом уже поймем, почему она работает: | ||
<syntaxhighlight lang="Python" line=true> | <syntaxhighlight lang="Python" line=true> | ||
| − | def rev(a, m) | + | def rev(a, m): |
if a == 1: return 1 | if a == 1: return 1 | ||
return (1 - rev(m % a, a) * m) / a + m | return (1 - rev(m % a, a) * m) / a + m | ||
Текущая версия на 08:47, 17 октября 2020
Обратный по любому модулю в 2 строчки
Реализация
Сначала приведем реализацию, а потом уже поймем, почему она работает:
1 def rev(a, m):
2 if a == 1: return 1
3 return (1 - rev(m % a, a) * m) / a + m
Идея
Первый случай очевиден. Во втором случае проверим правильность формулы: $1 - rev(m \% a, a) \cdot m$ делится на $a$, так как $rev(m \% a, a)$ — обратный к $m$ по модулю $a$. При этом $\frac{rev(m \% a, a) \cdot m}{a}$ делится на $m$, так что итоговое выражение сравнимо с $\frac{1}{a}$ по модулю $m$. Почему ответ всегда будет получаться именно в диапазоне от $0$ до $m - 1$, мы оставим читателю в качестве упражнения.
Асимптотика алгоритма $O(\log m)$, потому что он эквивалентен Алгоритму Евклида по вызовам рекурсии.
Автор конспекта: Егор Горбачев
По всем вопросам пишите в telegram @Peltorator