Поиск факториала по простому модулю за $O(\sqrt{\min (p, n)} \log^2 n)$
В прошлом разделе мы научились искать $n! \mod p$ без вхождений $p$ в факториал за $O(p \log_p n)$ или за $O(p + \log_p n)$, если заранее предпосчитать все факториалы. Однако чаще всего модуль — это число порядка $10^9$, поэтому эти алгоритмы нам не подходят. Давайте научимся искать факториал быстрее.
Давайте сначала научимся искать $n! \mod p$ за $O(\sqrt{n} \log^2 n)$, если $n < p$.
Обозначим $k = \left\lfloor \sqrt{n} \right\rfloor$. Тогда мы хотим построить алгоритм за $O(k \log^2 k)$. Пусть $n = k^2 + b$, где $b \le 2 \cdot k$. В таком случае нам достаточно посчитать $\left(k^2\right)!$, а затем за $O(k)$ домножить его на $b$ недостающих чисел.
Построим многочлен $P(x) := (kx) \cdot (kx - 1) \cdot \ldots \cdot (kx - k + 1)$. Тогда $\left(k^2\right)! = P(1) \cdot P(2) \cdot \ldots \cdot P(k)$. Введем еще один многочлен $Q(x) := P(2x) \cdot P(2x - 1)$. Получается, что $\left(k^2\right)! = Q(1) \cdot Q(2) \cdot \ldots \cdot Q\left(\frac{k}{2}\right)$, если $k$ четно, а если $k$ нечетно, то еще нужно домножить на $P(k)$, но его мы легко можем сделать за $O(k)$.
Теперь давайте рекурсивно запустимся от многочлена $Q$. Глубина рекурсии будет $\log k$. Однако проблема в том, что изначально многочлен $P$ имел степень $k$, однако многочлен $Q$ имеет степень уже $2k$, и степень будет возрастать. Но если учесть, что многочлен $Q$ нам нужно посчитать только в точках $1, 2, \ldots, \left\lfloor \frac{k}{2} \right\rfloor$, то можно взять вместо $Q$ многочлен $Q \bmod (x - 1) \cdot (x - 2) \cdot \ldots \cdot (x - \left\lfloor \frac{k}{2} \right\rfloor)$. И у такого многочлена уже степень будет $< \left\lfloor \frac{k}{2} \right\rfloor$.
Взятие двух многочленов по модулю можно реализовать за $O(k \log^2 k)$ через деление. Тогда асимптотика алгоритма получается $O\left(k \log^2 k + \frac{k}{2} \log^2 \left( \frac{k}{2} \right) + \frac{k}{4} \log^2 \left(\frac{k}{4} \right) + \ldots\right) = O\left(\left(k + \frac{k}{2} + \frac{k}{4} + \ldots\right) \log^2 k\right) = O(k \log^2 k)$. Что и требовалось.
Чтобы получить алгоритм, который работает при $n \ge p$, нужно просто применить алгоритм из предыдущего раздела, однако вычислять $b!$ с помощью нового метода. $b < p$, поэтому это вычисление будет работать не дольше $\sqrt{p} \log^2 p$. Всего итераций будет $\log_p n$, так что асимптотика получается $O(\sqrt{p} \log^2 p \cdot \log_p n) = O\left(\sqrt{p} \log^2 p \frac{\log n}{\log p}\right) = O\left(\sqrt{p} \log p \log n\right)$. Если объединить случаи $p < n$ и $p \ge n$, получается время работы $O\left(\sqrt{\min (p, n)} \log \min (p, n) \log n\right)$.