pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

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

ユークリッドの互除法(a,b)->(b,a-floor(a/b)*b) という変換を繰り返すアルゴリズムである。この変換は行列 A={{0,1},{1,-floor(a/b)}}を用いて (a',b')=A(a,b)と書ける。これを繰り返し行うため、互除法の過程は(1,0)=...DCBA(a,b)のような行列積で表せる。

(a,M) で互除法を走らせる。互除法の過程は mod M の上で (1,0)=...DCBA(a,M)=...DCBA(a,0) となる。...DCBAの(1,1)要素を見れば逆元が得られる。

int modinv(int a, int b=mod, int x=1, int y=0) {
	if (b==0) return x<0 ? x+mod : x;
	return modinv(b, a-a/b*b, y, x-a/b*y);
}