當m是質數時如何計算nPr mod m？

Question

我需要找出nPr％m的值。

這是我使用的方法。

查找，正！％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在產品兩個因素任何乘法的中間結果。

我不會在這裏提供完整的代碼，但希望這將足以讓你弄清楚。