コンパクトにmod逆元を求める

mod逆元を求めたいだけなのに繰り返し二乗法を書くのは面倒。そういうときに使える手法。素数mod限定。

long long modinv(long long n) {
	return n == 1 ? n : modinv(MOD % n) * (MOD - MOD / n) % MOD;
}

上の計算式は $M \bmod n + \lfloor M/n \rfloor n = M \equiv 0 \pmod{M}$ に基づいている(除法の原理)。mod 109+7 では再帰の深さが49以下であることを確認している。

計算量解析

雰囲気だけ書いておく。証明にはなっていないし、証明が存在するかどうかも知らない。

$M \bmod n \lt n/2$ を満たす $n$ の割合をコンピュータで計算してみると、約 $2-\log 4 \approx 0.6137$ だと分かる。$2-\log4$ の確率で値が半分になると仮定すると、再帰の深さの期待値は $\lg n/(2-\log4)$ になる。実際、mod 109+7での再帰の深さの最大値が49であるのに対して期待値は48.7161なので仮定は正しそうである。よって期待計算量は $O(\log n)$ と言えそうである。