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

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

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

上の計算式は M%n+⌊M/n⌋n=M≡0 (mod M) に基づいている(除法の原理)。mod 109+7 では再帰の深さが49以下であることを確認している。

計算量解析

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

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