subfactorial modulo prime(!n mod p)

Question

有没有一种简单的方法来实现!n mod p(紊乱的数量),where n ? 2?10^8并且p是一个主要和p < 1000

程序必须快速执行,因此天真的方法不起作用.

Answer 1

事实证明,这!n mod p是周期性的2p.因此,我们可以计算!n mod pas !(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]- modulo p,右边唯一的非零术语出现在哪里i=n.
• 得出结论!(n+2p) = !p !p !n = !n mod p.

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