エントリーの編集
![loading...](https://b.st-hatena.com/bdefb8944296a0957e54cebcfefc25c4dcff9f5f/images/v4/public/common/loading@2x.gif)
エントリーの編集は全ユーザーに共通の機能です。
必ずガイドラインを一読の上ご利用ください。
Python で mod の下での逆元を計算するテーブルを作成する - わかばめにっき
記事へのコメント0件
- 注目コメント
- 新着コメント
このエントリーにコメントしてみましょう。
注目コメント算出アルゴリズムの一部にLINEヤフー株式会社の「建設的コメント順位付けモデルAPI」を使用しています
![アプリのスクリーンショット](https://b.st-hatena.com/bdefb8944296a0957e54cebcfefc25c4dcff9f5f/images/v4/public/entry/app-screenshot.png)
- バナー広告なし
- ミュート機能あり
- ダークモード搭載
関連記事
Python で mod の下での逆元を計算するテーブルを作成する - わかばめにっき
wakabame.hatenablog.com では, の素数 で割った余りを求める方法について解説しました. 実は, この計算... wakabame.hatenablog.com では, の素数 で割った余りを求める方法について解説しました. 実は, この計算アルゴリズムは高速化できます. ボトルネックはどこか? の計算結果が何度も呼び出される場合を考えましょう. そのたびに 階乗の計算が必要になる 逆元を求めるために 乗の繰り返し二乗法が必要になる 点がボトルネックです. 前者は予め必要な大きさのリストを構築して, 計算結果を最初に持っておけば で済みます. 一方で, 後者のボトルネックについては, 繰り返し二乗法を全ての整数に対して行わなければならないのが(定数倍とはいえ)しんどいです. そこで, 次のブログを参考に逆元テーブルの構築を考えます. drken1215.hatenablog.com takapt0226.hatenablog.com 以後, を十分大きな素数とします. 逆元テーブルを構築するスクリプト