有没有一种简单的方法来实现!n mod p（错乱的数量）where n ≤ 2∗10^8并且p是素数和p < 1000
程序必须快速执行，这样幼稚的方法就行不通了。
user1721258
问问题
967 次
2 回答
8
事实证明，它!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。
于 2012-10-16T12:40:15.977 回答
0
有了递归公式（!n = (n - 1) (!(n-1) + !(n-2))），为什么不实现“模乘p”和“模加”运算p呢？
于 2012-10-16T12:02:20.460 回答