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のではなく、積の 2 つの要素を掛け合わせた中間結果を得ることができます。

ここでは完全なコードは提供しませんが、理解するにはこれで十分であることを願っています。