扩展欧几里得算法（exGcd）

扩展欧几里得算法（Extended Euclidean algorithm, EXGCD），常用于求 \(ax+by=c\) 的一组可行解。

过程

设
\(ax_1+by_1=\gcd(a,b)\)
\(bx_2+(a\mod b)y_2=gcd(b,a\mod b)\)
由欧几里得算法 : \(\gcd(a,b)=gcd(b,a \mod b)\)
所以 ： \(ax_1+by_1=bx_2+(a \mod b)y_2\)
又因为 : \(a \mod b=a-(\lfloor \frac{a}{b} \rfloor \times b)\)
所以 : \(ax_1+by_1=bx_2+((a-\lfloor \frac{a}{b} \rfloor \times b))y_2\)
\(ax_1+by_1=bx_2+ay_2-\lfloor \frac{a}{b} \rfloor \times by_2=ay_2+b(x_2-\lfloor \frac{a}{b} \rfloor y_2)\)
因为 \(a=a, b=b\) 所以 \(x_1=y_2, y1=x2-\lfloor \frac{a}{b} \rfloor y_2\)
那么就可以将这个过程一直进行下去，直到 \(\gcd\) 为 \(0\) 返回 \(x=1,y=0\)。

代码

int exGcd(int a, int b, int &x, int &y) {
	if (!b) {
		x = 1, y = 0; // gcd 为 0
		return a; 
	}
	int d = exGcd(b, a % b, x, y);
	int t = x;
	x = y;
	y = t - (a / b) * y;
	return d;
} 

例题

Luogu P5656 【模板】二元一次不定方程 (exgcd)

先用裴蜀定理检查是否有解，再用 exGcd 求特解，最后调整解，使得满足题目条件。
时间复杂度 \(O(log(N))\)

Luogu P1082 [NOIP2012 提高组] 同余方程

将 \(ax \equiv 1(\mod b)\) 变形成 \(ax+by=1\) 用 exGcd 解决就行了。