光速阶乘算法

· · 休闲·娱乐

摘要

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

实现

我们知道：

\binom{n}{\left\lfloor \frac{n}{2} \right\rfloor}=\frac{n!}{\left\lfloor \frac{n}{2} \right\rfloor!\left\lceil \frac{n}{2} \right\rceil!}

所以：

n!=\binom{n}{\left\lfloor \frac{n}{2} \right\rfloor}\left\lfloor \frac{n}{2} \right\rfloor!\left\lceil \frac{n}{2} \right\rceil!

后面的 \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 的值。