二項係数を mod p で書きたい！
二項係数 $${\binom{n}{k}}$$ を$${\text{mod}\ p}$$ で考えたくなることありますよね？
そんな人のために，二項係数を$${\text{mod}\ p}$$ で表示してくれるアプリを自作しました．
ただし，計算効率は悪いので，$${n}$$ を大きい値 (なんと 25 以上!!!) に設定すると，手計算の方が早いのではないかと思うレベルで時間がかかります．
ゆえに，改良の余地ありのアプリです．
数値実験用で，そんなに大きい値が必要なわけでもないので，今のところ改良する予定はありませんが．
なお，二項係数 $${\binom{n}{k}}$$ を$${\text{mod}\ p}$$ で表すことについては，Lucas の定理が知られています．$${p}$$ 進展開をして，各位で二項係数を計算し，その積をとればよいそうです:
$$
\displaystyle\binom{n}{k} = \prod_i \binom{n_i}{k_i},
$$
ただし，$${ n = n_0 + n_1p + n_2p^2 + \cdots }$$.
この記事が気に入ったらサポートをしてみませんか？