阶乘与取模

问题

给出N, P, 求[latex]N! mod P[/latex], 要求表示为[latex](x \mod P)\times P^t[/latex]。

问题一

暴力。

问题二

但是当N≤10^9时呢?
P是素数且小于10^7。
假如N=10, P=3:
$$ N! = 1\times 2\times 3\times 4\times 5\times 6\times 7\times 8\times 9\times 10 $$
按照P进行分段, 把拥有P作为因子的数字全部剔除, 扯到前面来变成这样:
这里因为[latex]3\times 6\times 9 = 3^{3(项数)}(1+2+3(倍数))[/latex], 所以有:
$$ N! = 3^3(1+2+3)(1\times 2\times 4\times 5\times 7\times 8\times 10) $$
称[latex]3^3[/latex]为A, [latex](1+2+3)[/latex]为B, 上面最后那一坨为C。
对于A可以直接计算。
对于C, 我们把它分段成这个样子:[latex](1\times 2)(4\times 5)(7\times 8)\times 10[/latex], 简而言之就是按照P来分段。
首先给出结论, 因为每一段内的所有数和P是互质的, 所以任何一段乘积对P取模都是同一个数。
证明: 对于第k段, 我们可以表示为[latex](kP+1)(kP+2)…(kP+(P-1)) = \prod_{i=1}^{P-1} (kP+i)[/latex]。
发现这个累积中, 每一项都由两项相加:k倍的P和i, 其中kP是P的倍数, 对P取模等于0。我们知道上面式子展开式的每一项必然至少包含未展开式中每一项中的至少一项。也就是说, 它如果不包含i就必须包含kP, 二选一。
那么展开式中的任何一项因子一旦包含一个kP, 这一项就是0了, 不用予以考虑。那么最后展开式的有效项只会剩下一个:[latex]\prod_{i=1}^{P-1} i[/latex](由未展开状态下的每一项的第二项, 也就是i, 乘起来)。
所以每段对P取模都是相等的, 我们只需要使用O(P)的时间把这个东西计算出来然后快速幂就可以计算C了。
对于B, 发现这是一个完全相同的阶乘子问题, 不过规模除以了P, 递归处理即可。
复杂度应该是[latex]O(max\{P, log_P(N)\})[/latex]的。

问题三

P等于一个素数p的T次方且p小于10^7。
和问题二的处理方式类似, 这次处理B部分时按照P进行分段, 然后每一段对P取模依然是相等的, 证明类似。

问题四

P等于[latex]\prod_{i=1}^T p_i^{t_i}[/latex], 且[latex]\forall i, p_i^{t_i} \le 10^7[/latex]。
上CRT!