Перечислю все практические методы вычисления остатка $n!\mathrm{mod}p$ (где $p$ — простое), укажу формулы, условия применимости и оценю эффективность.
1) Легендрова формула — проверка делимости
- Формула для показателя простого $p$ в разложении $n!$:
$$v_p(n!)=\sum _{k\ge 1}\lfloor \frac{n}{p^k}\rfloor .$$ - Следствие: $n!\equiv 0(\mathrm{mod}p)$ тогда и только тогда, когда $v_p(n!)\ge 1$, т.е. если и только если $n\ge p$.
- Применимость: всегда; быстрый тест на ноль (O(${\log }_{p}n$) операций).
- Эффективность: очень высокая для определения нулевого остатка.
2) Прямое умножение (итеративное)
- Для $0\le n<p$:
$$n!\equiv \prod _{k=1}^{n}k(\mathrm{mod}p).$$ - Реализация: последовательное умножение с редукцией по модулю — $O(n)$ по количеству умножений.
- Применимость: когда $n$ «маленькое» по сравнению с затратами (например $n\lesssim 10^7$ в одноточечных задачах на современных машинах).
- Эффективность: простая и надёжная; линейная по $n$.
3) Использование теоремы Вильсона (обращение хвоста)
- Теорема: $(p-1)!\equiv -1(\mathrm{mod}p)$.
- Для $0\le n<p$ из $(p-1)!=n!\cdot {\prod }_{k=n+1}^{p-1}k$ получаем
$$n!\equiv -(\prod _{k=n+1}^{p-1}k{)}^{-1}(\mathrm{mod}p).$$ - Практическое применение: если $p-1-n$ значительно меньше $n$, выгодно посчитать хвост $P={\prod }_{k=n+1}^{p-1}k$ (это $O(p-1-n)$ умножений) и найти обратное $P^{-1}$ (одна евклидова/быстрая степень за $O(\log p)$). Для ответа берём $-P^{-1}$.
- Эффективность: оптимально, когда $p-1-n\ll n$. Общая стратегия: выбрать минимум между прямым вычислением и вычислением хвоста плюс инверсия — требуется примерно $\min (n,p-1-n)$ умножений.
4) Специальные формулы для «половинного» факториала
- Для $n=(p-1)/2$ есть тождество (разбиение на пары $i(p-i)$):
$$(\frac{p-1}{2}!{)}^2\equiv (-1{)}^{\frac{p+1}{2}}(\mathrm{mod}p).$$ - Значит $\frac{p-1}{2}!$ равен некоторому квадратичному корню RHS; знак/корень восстанавливают через алгоритм извлечения квадратного корня по модулю $p$ (Tonelli–Shanks).
- Применимость: только для $n=(p-1)/2$; полезно при необходимости точного значения в этом частном случае.
- Эффективность: логарифмическая для Tonelli–Shanks, плюс проверка квадратичести.
5) Предвычисления (много запросов)
- Если нужно много значений $n!\mathrm{mod}p$ для разных $n$ (и $p$ фиксирован): предвычислить массив factorials до $p-1$:
$$fact[0]=1,fact[i]=fact[i-1]\cdot i(\mathrm{mod}p)(1\le i\le p-1).$$ Время/память: $O(p)$. Тогда ответ за $O(1)$.
- Если нужно обратные факториалы, можно также предвычислить inverses и invfact за $O(p)$.
- Применимость: множество запросов, $p$ достаточно мал или доступна память $O(p)$.
6) Быстрое умножение через «product tree» / деление и владычество (для очень больших $n,p$)
- Метод: строят дерево произведений отрезков (product tree) и затем вычисляют конечный остаток через деление дерева; либо используют алгоритмы быстрого умножения больших блоков (FFT/NTT) для ускорения умножений длинных последовательностей.
- Асимптотика (теоретическая): примерно $O(M(t)\log t)$, где $t$ — число множителей (≈$n$ или $p$) и $M(t)$ — время умножения чисел нужной длины. На практике при модульных умножениях машинного слова выигрыш небольшой; метод оправдан, если нужно вычислять факториалы при экстремально больших параметрах и применяются быстрые многоточечные умножения.
- Применимость: когда $p$ очень большой и требуется асимптотически лучшее решение; сложная реализация.
7) Выводы и сравнение эффективности (практические рекомендации)
- Если $n\ge p$: ответ сразу $0$ (Лежандр).
- Если $n<p$:
- Если $n$ мал (например $n\lesssim 10^7$ или приемлемо время $O(n)$): используйте прямое умножение.
- Если $p-1-n$ мал: используйте хвост + инверсию по Вильсону (т.е. вычислить $P={\prod }_{k=n+1}^{p-1}k$ и взять $-P^{-1}$).
- Если требуется много запросов при фиксированном $p$: предвычислите таблицу факториалов за $O(p)$.
- Частный случай $n=(p-1)/2$: используйте формулу с квадратом и Tonelli–Shanks для получения значения быстрее, чем прямое умножение до $(p-1)/2$ в ряде случаев.
- Для экстремально больших параметров и асимптотических требований — product-tree / быстрые умножения (сложная реализация).
- Сводная сложность (одноточечное вычисление при $n<p$):
- прямое: $O(n)$ мультипликативных шагов;
- хвост (Вильсон): $O(p-1-n)$ + $O(\log p)$ для инверсии;
- предвычисление: $O(p)$ предобработки + $O(1)$ запрос;
- product-tree: асимптотически лучше при очень больших размерах, но хуже по константам и сложности реализации.
Короткая инструкция выбора:
- Проверить $n\ge p$ → ноль.
- Иначе взять стратегию с минимальным числам умножений: либо прямой продукт длины $n$, либо хвост длины $p-1-n$ + одна инверсия; для множества запросов — предвычисление.
Если нужно, могу привести короткие код‑шаблоны (C++/Python) для каждого метода.