逆元(ユークリッドの互除法)

目的

整数$M$と互に素な整数$a$について、$ax=1\mod M$なる整数$x$を$O(\log M)$で求めます。フェルマーの小定理は$M$が素数の時しか使えなかったので、こちらの方が適応範囲が広いです。

計算量

$O(\log M)$

使い方

long mo
目的の項の$M$に相当します。
long a
目的の項の$a$に相当します。
long inv(long a,long mo)
$a^{-1}\mod mo$をreturnします。

ソースコード

long inv(long a, long mo) {
	a %= mo;
	long[] v = { 0, 1, mo };
	long[] u = { 1, 0, a };
	while (v[2] != 1) {
		if (v[2] < u[2]) {
			long[] tmp = Arrays.copyOf(v, v.length);
			v = u;
			u = tmp;
			continue;
		}
		long coe = v[2] / u[2];
		for (int i = 0; i < 3; ++i) {
			v[i] = v[i] - u[i] * coe;
		}
	}
	return v[0] < 0 ? v[0] + mo : v[0];
}