光速阶乘算法

一种能在模数较小时 $O(\log n\log_p{n})$ 求出 $n!$ 的算法。

我们知道：

所以：

后面的 $\left\lfloor \frac{n}{2} \right\rfloor!\left\lceil \frac{n}{2} \right\rceil!$ 可以根据 $n$ 的奇偶性化为 $(\left\lfloor \frac{n}{2} \right\rfloor!)^2$ 或 $(\left\lfloor \frac{n}{2} \right\rfloor!)^2\left\lceil \frac{n}{2} \right\rceil$。

这个是可以递归计算的。

而前面的 $\binom{n}{\left\lfloor \frac{n}{2} \right\rfloor}$ 一般情况下并没有什么好的计算方法，但我们可以使用 Lucas 定理在模数较小的情况下在 $O(\log_p{n})$ 的时间内求出它的值。

至多递归 $O(\log n)$ 层，每层使用 Lucas 定理是 $O(\log_p{n})$ 的，所以总复杂度是 $O(\log n\log_p{n})$ 的。

相比于休闲娱乐区前几篇光速阶乘算法，这个方法具有可行性且实际优化了复杂度。

相比于传统的快速阶乘算法的 $O(\sqrt{n}\log n)$，这个方法更快，在 $p=10^4+7$ 时，我们也可以在可接受的时间内计算出 $n=10^{18}$ 时 $n!\bmod p$ 的值。