当m是素数时，如何计算nPr模m？

Question

我要找出nPr%的价值。

这就是我使用的方法。

找到，n!%m，(n-r)!%m并将它们分开

但是，在某些情况下，( nPr )%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。

我不会在这里提供完整的代码，但希望这足以让您解决它。