光速阶乘算法

\textbf{Light Speed Calculation of Factorial} \text{Rain chr}

前言

怎么投稿到休闲娱乐区？

摘要

本论文介绍一种在 O(\log_p n) 时间内求 n! 的方法。

引入

引理 1（组合数公式^1） 对于满足 0 \leqslant m \leqslant n 的整数 n, m，有

\binom n m = \frac {n!} {m! (n - m)!}

证明 根据组合意义，证毕。

这启示我们将较大的数的阶乘与较小的数的阶乘建立关系，以优化计算阶乘的时间。

算法

定理 1（光速阶乘算法） 把 m = n 代入引理 1，即 \binom {2n} {n} = \frac {(2n)!} {(n!)^2}，移项得到

(n!)^2 = \frac{(2n)!} {\binom {2n} n }

设 f(n)=n!，则可以建立递推式：

f(n)^2=\frac {f(2n)} {\binom {2n} n }

随着问题规模增大，我们可以在不超过 O(\log_p n) 次扩大之后知道最终 f(2n) 和 {\binom {2n} n } 在取模意义下的结果，于是可以再以 O(\log_p n) 的时间复杂度内回溯求出 f(n) 的值。

复杂度分析

我们运用了化归的思想，将一个小问题规约为了大问题，得到了一个复杂度仅仅为 O(\log_p n) 的光速阶乘算法。

应用

本算法可以用于一切需要计算阶乘的地方，适用性极强。

前景

随着计算组合数方面研究的深入，本算法将有望变得更为厉害。

总结

光速阶乘算法是一种优秀的计算阶乘的方式，它充分利用化归思想，并因此具有极高的可拓展性。

致谢

感谢 modfisher^a，bluewindde ^b，_zdc_^c 对本论文重要结论作出的贡献。

$^b$ https://www.luogu.com.cn/user/857577 $^c$ https://www.luogu.com.cn/user/431487 ## 参考文献 [1] [组合数公式](https://www.bilibili.com/video/BV1GJ411x7h7) [2] [等比数列求和公式](https://www.bilibili.com/video/BV1qU4y1F73A) [3] [龟速阶乘算法](https://www.luogu.com/article/h3prgowm) 作者：Yile_Wang 2024 年 11 月 15 日 16 时 21 分于机房