Python で mod の下での逆元を計算するテーブルを作成する - わかばめにっきwakabame.hatenablog.com では, の素数 で割った余りを求める方法について解説しました. 実は, この計算アルゴリズムは高速化できます. ボトルネックはどこか？ の計算結果が何度も呼び出される場合を考えましょう. そのたびに 階乗の計算が必要になる 逆元を求めるために 乗の繰り返し二乗法が必要になる 点がボトルネックです. 前者は予め必要な大きさのリストを構築して, 計算結果を最初に持っておけば で済みます. 一方で, 後者のボトルネックについては, 繰り返し二乗法を全ての整数に対して行わなければならないのが（定数倍とはいえ）しんどいです. そこで, 次のブログを参考に逆元テーブルの構築を考えます. drken1215.hatenablog.com takapt0226.hatenablog.com 以後, を十分大きな素数とします. 逆元テーブルを構築するスクリプト
