Обратное число к а по модулю m
Обратное число Даны два целых числа m и a. Если не существует обратного числа к a по модулю m, то выведите число −1, а если существует, то выведите это число (ответ должен лежать в границах от 0 до m−1). Входные данные В единственной строке входных данных даны два целых числа 1 Выходные данные Выведите ответ на задачу. Примеры Ввод 179 57 Вывод 22
b = 0 a = list(map(int, input().split())) b = pow(a[1], a[0] - 2, a[0]) if pow(a[1], a[0] - 2, a[0]) == 0: print(-1) else: print(b) Отслеживать
34k 3 3 золотых знака 20 20 серебряных знаков 56 56 бронзовых знаков
Обратный по модулю
Фактическая польза от обратного по модулю в том, что он заменяет деление. А именно, если нам в рамках вычислений хочется найти значение $\frac \pmod
$, то мы считаем это значение эквивалентным значению $A \cdot B^ \pmod
$.
Чтобы найти обратное по модулю, есть несколько разных техник, но самая популярная — теорема Эйлера:
Теорема Эйлера
Или это же выражение для простого модуля $p$ называется малой теоремой Ферма:
Малую теорему Ферма можно достаточно просто доказать комбинаторно. Поставим другую задачу — подсчет числа способов раскрасить $p$-угольник в $a$ цветов. Раскрасим каждую вершину в какой-то цвет. Всего таких раскрасок $a^p$. Заметим, что поскольку $p$ простое, то у всех раскрасок, кроме тех, где все раскрашено в один цвет поворотом получается ровно $p$ раскрасок. Значит всего различных раскрасок $\frac
+ a$. Это число должно быть целым, а значит $a^p — a$ делится на $p$, откуда $a^
— 1 \equiv 0 \pmod
$.
Как теперь научиться делить? Все просто:
Значит, для простых $p$ достаточно посчитать $a^$ с помощью быстрого возведения в степень
Диофантово уравнение
Альтернативный вариант — свести уравнение $ax \equiv 1 \pmod
$ к диофантову уравнению $$ ax + py = 1$$
Обратный элемент по модулю
Часто в задачах требуется посчитать что-то по простому модулю (чаще всего \(10^9 + 7\) ). Это делают для того, чтобы участникам не приходилось использовать длинную арифметику, и они могли сосредоточиться на самой задаче.
Обычные арифметические операции выполняются не сильно сложнее — просто нужно брать модули и заботиться о переполнении. Например:
c = (a + b) % mod; c = (mod + a - b) % mod; c = a * b % mod;Но вот с делением возникают проблемы — мы не можем просто взять и поделить. Пример: \(\frac = 4\) , но \(\frac \neq 4\) .
Способ 1: бинарное возведение в степень
Если модуль \(p\) простой, то решением будет \(a^ \equiv a^\) . Это следует из малой теоремы Ферма:
Теорема. \(a^p \equiv a \pmod p\) для всех \(a\) , не делящихся на \(p\) .
Доказательство. (для понимания несущественно, можно пропустить)
Здесь \(P(x_1, x_2, \ldots, x_n) = \frac<\prod (x_i!)>\) это мультиномиальный коеффициент — количество раз, которое элемент \(a_1^ a_2^ \ldots a_n^\) появится при раскрытии скобки \((a_1 + a_2 + \ldots + a_n)^k\) .
Теперь два раза «поделим» наш результат на \(a\) .
\[ a^p \equiv a \implies a^ \equiv 1 \implies a^ \equiv a^ \]
Получается, что \(a^\) ведет себя как \(a^\) , что нам по сути и нужно. Посчитать \(a^\) можно за \(O(\log p)\) бинарным возведением в степень.
Приведем код, который позволяет считает \(C_n^k\) .
int t[maxn]; // факториалы, можно предподситать простым циклом // бинарное возведение в степень int bp (int a, int n) int res = 1; while (n) if (n & 1) res = res * a % mod; a = a * a % mod; n >>= 1; > return res; > // находит обратный элемент как a^(p-2) int inv (int x) return bp(x, mod-2); > int c (int n, int k) return t[n] * inv(t[k]) % mod * inv(t[n-k]) % mod; >Способ 2: диофантово уравнение
Диофантовыми уравнениями называют такие штуки:
Требуется решить их в целых числах, то есть \(a\) и \(b\) известны, и нужно найти такие целые (возможно, отрицательные) \(x\) и \(y\) , чтобы равенство выполнялось. Решают такие вещи расширенным алгоритмом Евклида. TODO: описать, как он работает.
Подставим в качестве \(a\) и \(b\) соответственно \(a\) и \(m\)
Одним из решений уравнения и будет \(a^\) , потому что если взять уравнение по модулю \(m\) , то получим
\[ ax + by = 1 \iff ax \equiv 1 \iff x \equiv a^ \pmod m \]
Преимущества этого метода над возведением в степень:
- Если обратное существует, то оно найдется даже если модуль не простой. Способ с бинарным возведением тоже можно заставить работать с произвольным модулем, но это будет намного труднее.
- Алгоритм проще выполнять руками.
Сам автор почти всегда использует возведение в степень.
Почему \(10^9+7\) ?
- Это выражение довольно легко вбивать ( 1e9+7 ).
- Простое число.
- Достаточно большое.
- int не переполняется при сложении.
- long long не переполняется при умножении.
Кстати, \(10^9 + 9\) обладает теми же свойствами. Иногда используют и его.
Предподсчёт обратных факториалов за линейное время
Пусть нам нужно зачем-то посчитать все те же \(C_n^k\) , но для больших \(n\) и \(k\) , поэтому асимптотика \(O(n \log m)\) нас не устроит. Оказывается, мы можем сразу предподсчитать все обратные ко всем факториалам.
Если у нас уже написан inv , то нам не жалко потратить \(O(\log m)\) операций, посчитав \(m!^\) .
int f[maxn]; f[0] = 1; for (int i = 1; i maxn; i++) f[i] = i*f[i-1] % mod; int r[maxn]; r[maxn-1] = inv(f[maxn-1]) for (int i = maxn-1; i >= 1; i--) r[i-1] = r[i]*i % mod;TODO: техника с сайта емакса.
RSA с нуля
при этом числа и должны быть взаимно простыми. Это значит, что не делится на . Соответственно единственный их общий делитель (он же наибольший) — это 1.
Для расчета обратного числа по модулю применяется расширенный алгоритм Евклида и соотношение Безу.
Соотношение Безу говорит, что существуют такие целые числа , , которые удовлетворяют следующему выражению:
Для нашего случая:
Если взять левую и правую часть по модулю , то
Чтобы найти наше обратное, нам нужно вычислить коэффициент в соотношении Безу.
Иногда получается отрицательным, можем взять его положительный модуль по без ущерба для исходного уравнения.