整数
この記事では, を素数とし, の下での割り算について述べます. 整数 に対する の下での割り算 では, 分数 が既約分数になっていなくても計算結果は変わりません. そのことを述べていきます. 復習 wakabame.hatenablog.com でも触れましたが, まずは逆元とは何…
wakabame.hatenablog.com では, の素数 で割った余りを求める方法について解説しました. 実は, この計算アルゴリズムは高速化できます.
注意:この記事は未完成です。こちらの記事を参考にお願いします wakabame.hatenablog.com の素数 で割った余りを求める方法について解説します. は" 個の異なるものから 個を選ぶときの組み合わせの数"を表しており, 階乗記号 を用いて,と表されます. 階乗…
整数 と整数 に対して, を整数 で割った余りを出力します. 安直に を 回乗じてからで割れば良いのではないかと考えたくなりますが, この方法には2つの欠点があります. 回乗じるのに計算量が かかってしまう. は処理しきれなくなるくらい大きくなりえる. この…