extgcd.hpp ファイル

#include "../../kyopro_library/template.hpp"

[ソースコード]

関数
tuple< ll, ll, ll >	ExtGcd (ll a, ll b)
	拡張ユークリッドの互除法
ll	ModInvGcd (ll a, ll m)
	mod 逆元

関数詳解

ExtGcd()

tuple< ll, ll, ll > ExtGcd	(	ll	a,
		ll	b )

拡張ユークリッドの互除法

gcd(a,b) = gcd(ba,a), gcd(b,0) = b と ba + (b/a)*a = b を使う。 ax + by = g なる x,y を求めたい。 今、(ba)X + aY = g なる X, Y が分かっている。 (ba)X = bX - (b/a)*a*X より、これを代入して、 bX - (b/a)*a*X + aY = g a(Y-(b/a)*X) + bX = g

extgcd.hpp の 14 行目に定義があります。

ModInvGcd()

ll ModInvGcd	(	ll	a,
		ll	m )

mod 逆元

a^(-1) (mod m)

覚え書き

gcd(a,m)=1 でない場合、-1 を返す。

extgcd.hpp の 23 行目に定義があります。