factorial - 当 m 是素数时，如何计算 nPr mod m？

Question

我需要找出 nPr%m 的值。

这是我使用的方法。

找到, n!%m, (nr)!%m 并将它们分开

但是，在某些情况下，(nr)!%m 大于 n!%m，因此结果 nPr 为 0。

那我需要做什么？

Answer 1

这更像是一个数学问题而不是编程问题，但无论如何。

注意

n! / (n - r)! = n * (n - 1) * ... * (n - r + 1)

现在乘法，

(a * b * c) % m = (((a * b) % m) * c) % m

即，您可以得到乘积中两个因子的任意乘积的中间结果，而不是mod m整个乘积。mod m

我不会在这里提供完整的代码，但希望这足以让你弄清楚。