Обратные ко всем остаткам за O(p)

Обратные ко всем остаткам за $O(p)$

Идея

Сначала докажем следующий факт: $(p - 1)! \equiv -1 (mod \ p)$. Действительно, все остатки кроме $1$ и $-1$ разбиваются на пары вида $a$ и $a^{-1}$ (Если бы еще какой-то остаток стоял с собой в паре, то выполнялось бы $a^2 \equiv 1 (mod \ p)$, но тогда $p | (a - 1) \cdot (a + 1)$. Это верно только для $a \equiv \pm 1(mod \ p)$). Если перемножить по парам, получится $a \cdot a^{-1} \equiv 1 (mod \ p)$. Тогда итого $(p - 1)! \equiv -1 \cdot 1 \cdot 1 \cdot 1 \ldots \cdot 1 \equiv -1 (mod \ p)$.

Тогда $((p - 1)!)^{-1} \equiv -1 (mod \ p)$. Также заметим, что $\frac{1}{(k - 1)!} = \frac{k}{k!}$ и $\frac{(k - 1)!}{k!} = \frac{1}{k}$, так что по первому равенству мы можем вычислить обратные факториалы ко всем остаткам от $p - 1$ до $1$, после чего также предпосчитать все факториалы и вычислить обратные по модулю как $(k - 1)! \cdot (k!)^{-1}$.

---

Автор конспекта: Егор Горбачев

По всем вопросам пишите в telegram @Peltorator