無限に同じ内容の記事があると思います
二項係数の前計算などでよく使う, $1, 2, \cdots, n$ の $\mod p$ での逆元を前計算するやつ, ありますよね
$a ^ {-1} \equiv -(p \% a) ^ {-1} \times (p // a)\pmod p$
のように計算できるので, $a$ の小さいほうから順に計算しながらテーブルを埋めていくことで, 全体で $\Theta(n)$ で計算できます
($//$ は切り捨て除算, $\%$ は割った余りを指しています)
ところで何でこんなキモイ式なんでしょうか ぱっと見わからん気がします (僕だけですか？)
最近ライブラリ整備をしていてこれを書かされることが多くなったので, ちょっと整理します
$p = (p // a)\times a + (p \% a)$
と書けるのはわかると思います
$\text{mod}$ を取って
$0 \equiv (p // a)\times a + (p \% a) \pmod p$
いい感じに移項したら
$a ^ {-1} \equiv -(p \% a) ^ {-1} \times (p // a)\pmod p$
になりました おしまい
ところでこれは $a \le 1$ のときに死にますね (一敗)