逆元の列挙

目的

Z/(pZ)の逆元をnまで、$O(n)$で列挙します。

計算量

$O(n)$

使い方

long MODULO
目的の項のpに相当します。
long[] inv
inv[i]=$i^{-1} \mod {MODULO}$

ソースコード

long MODULO;
final int n = 2000;
long[] inv = new long[n];
for (int i = 2; i < n; ++i) {
	inv[i] = MODULO - (MODULO / i) * inv[(int) (MODULO % i)] % MODULO;
}