algorithm - 次阶模素数 (!n mod p)

Question

有没有一种简单的方法来实现!n mod p（错乱的数量）where n ≤ 2∗10^8并且p是素数和p < 1000

程序必须快速执行，这样幼稚的方法就行不通了。

Answer 1

事实证明，它!n mod p是周期性的，周期为2p。因此，我们可以计算!n mod p为!(n mod 2p) mod p，我们使用失调的递归公式来计算!n = (n-1) (!(n-1) + !(n-2))。

为了证明：

• 通过紊乱的递归关系观察到!(p+1) = 0 mod p。
• 工作模 p，!(n+p) = !p * !n（这可以使用前面的观察归纳证明）。
• 观察那个!p = -1 mod p。维基百科提供了一个公式：!n = n! - Sum[(n choose i) * !(n-i), i=1..n]-- 模 p，右侧唯一的非零项出现在哪里i=n。
• 得出结论!(n+2p) = !p !p !n = !n mod p。

从证明中，我们看到我们实际上可以计算!n = ± !(n mod p) mod p当n mod 2p小于时符号为正的位置p。

Answer 2

有了递归公式（!n = (n - 1) (!(n-1) + !(n-2))），为什么不实现“模乘p”和“模加”运算p呢？