Mae向きなブログ

Mae向きな情報発信を続けていきたいと思います。

Lucasの定理を用いて、nCr(mod p)を求めるPythonスクリプト

Python

Lucasの定理を用いて{}_nC_r \pmod pを求めるPythonスクリプトを作ってみました。

lucas.py

7行目は、フェルマーの小定理 b^{p-1} \equiv 1 \pmod pより、

a\cdot b^{p-2}\equiv a\cdot b^{-1} \pmod p

を用いています。(p:素数)

実行

% python lucas.py
13 3 3
1

参考