扩展欧几里德

文艺复兴

在$a$与$b$互质(即$gcd(a,b) = 1$)的情况下

(ax equiv 1 pmod b)

求$x$

(ecause ax equiv 1 pmod b)

( herefore ax - b(-y) = 1)

( herefore ax + by = 1)

(ecause gcd(a,b) = 1)

( herefore ax + by = gcd(a, b))

(ecause gcd(a, b) = gcd(b, a \% b))

[ egin{aligned} herefore ax + by &= bx + (a \% b) y \ &= bx + (a - lfloor dfrac a b floor imes b) y \ &= bx + ay - lfloor dfrac a b floor by \ &= ay + b(x - lfloor dfrac a b floor y) end{aligned} ]

( herefore x_1=y_2, y_1=x_2-lfloordfrac{a}{b} floor y_2)

void exgcd(int a, int b, int &x, int &y) {
	if (!b) return x = 1, y = 0, void();
	exgcd(b, a % b, x, y);
	int t = x;
	x = y;
	y = t - a / b * y;
}