В модулярной арифметике в отличие от вычитания, сложения и умножения нельзя просто так делить. Для этого необходимо найти обратный по модулю элемент и умножить на него.
Допустим дано число \(a\) в модулярной арифметике по простому модулю \(m\). Необходимо найти такое \(a^{-1}\), что \(a^{-1} * a = 1\).
В следствии малой теоремы Ферма для всех простых \(m\) верно \(a^{m-2} = a^{-1} \pmod{m} \)
С помошью бинарного возведения в степень можно получить обратное по модулю число за \(O(\log{m})\).
Пусть \(a^{-1} = x\), тогда нам надо решить диофантового уравнение: \( a * x + m * y = 1\)
Асимптотика: \(O(\log{m})\).
Допустим нам надо за линию посчитать все обратные по модулю \(m\) от \(1\) до \(m-1\).
Предподсчитаем факториалы до \(m-1\). Теперь посчитаем с помощью одного из вышеописанных методов за \(O(\log{m})\) обратное по модулю \((m-1)!\)
Последовательно домножая на \(m-2, m-3 ... 2\) можно получить все обратные факториалы.
Теперь заметим, что \( (p-1)! * \frac{1}{p!} = \frac{1}{p} \).
Так, за \( O(m + \log{m}) = O(m) \) мы предподсчитали все обратные по модулю.
Обозначим \(rev[i]\) за обратное по модулю. Тогда выполняется \(rev[i] = - \lfloor \frac{m}{i} \rfloor * rev[m \% i] \).
\( m \% i = m - \lfloor \frac{m}{i} \rfloor * i \)
\( m \% i \equiv -\lfloor \frac{m}{i} \rfloor * i \pmod{m} \)
\( m \% i * i^{-1} * (m \% i)^{-1} \equiv -\lfloor \frac{m}{i} \rfloor * i * i^{-1} * (m \% i)^{-1} \pmod{m} \)
\( i^{-1} \equiv -\lfloor \frac{m}{i} \rfloor * (m \% i)^{-1} \pmod{m} \)
Теперь заменим обратные величины на \(rev[i]\):
\( rev[i] = -\lfloor \frac{m}{i} \rfloor * rev[m \% i] \)
Этот способ, несомненно, лаконичнее.
Асимптотика: \(O(n) = O(m)\)