ルーカスの定理

3行要約

1. 二項係数を素数pで割った余りを、p進展開を用いて計算する定理。
2. 大きなn, kに対する二項係数の合同式を高速に求めることができる。
3. 数論や組合せ論、競技プログラミングのアルゴリズムで利用される。