扩展欧几里得算法(exgcd)

扩展欧几里得算法，是用来求形如

[ax+by=c ]

的不定方程的整数解的。

判断是否有整数解

根据裴蜀定理，若 (gcd(a,b) mid c)，则一定有整数解，否则一定无解。

证明

设 (d=gcd(a,b))，显然有 (d mid a,d mid b)。由于 (x,y) 都是整数，所以 (d mid (ax),d mid (by))。
所以如果要让式子成立，(c) 必须得是 (a,b) 的公约数的倍数才对。
又因为 (x,y) 是整数，所以 (c) 必须是 (a,b) 的最大公约数的倍数才行。
实在看不懂的话感性理解下吧awa

转化

让方程两边同除以 (gcd(a,b))，可以得到方程

[a'x+b'y=c' ]

其中

[a'=a imes frac{gcd(a,b)}{c},b'=b imes frac{gcd(a,b)}{c},c'=c imes frac{gcd(a,b)}{c}=gcd(a,b) ]

后面求特解中提到的方程均为转化后的方程，即后面方程中的 (a) 就是 (a')，(b) 就是 (b')

求解

求特解

由欧几里得算法可知，(gcd(a,b)=gcd(b,a mod b))
于是，我们可以得到

[bx'+(a mod b)y'=gcd(b,a mod b) ]

接下来我们就要根据 (x',y') 来反推 (x,y)。
因为 (gcd(a,b)=gcd(b,a mod b))，所以

[ax+by=bx'+(a mod b)y' ]

我们把右边的式子变形一下：

[bx'+(a mod b)y' ]

[=(a-bleftlfloorfrac{a}{b} ight floor)y'+bx' ]

[=ay'+bx'-bleftlfloorfrac{a}{b} ight floor y' ]

[= ay'+b(x'-leftlfloorfrac{a}{b} ight floor y') ]

所以，(x=y',y=x'-leftlfloorfrac{a}{b} ight floor y'))。
于是我们只要向欧几里得算法那样递归，就能得到一组特解了。
但还有一个问题，就是递归边界。
递归边界显然是 (b=0) 的情况，而此时的方程就变为：

[ax+by=ax=gcd(a,0)=a ]

所以此时 (x=1)，(y) 是任意整数。

求解过程用代码写出来就是这个亚子：

ll exgcd(ll a,ll b,ll &x,ll &y)
{
	if(b==0)
	{
		x=1;
		y=0;//y可以是任意整数，这里我们让他等于0也可以
		return a;
	}
	const ll m=exgcd(b,a%b,y,x);
	y-=(a/b)*x;
	return m;
}

但是但是，这求的是

[ax+by=gcd(a,b) ]

的解呀。不是我们要的解。
因为我们在转化时让方程两边都除以 (frac{c}{gcd(a,b)})，所以现在要乘回来：

[x=x imes frac{c}{gcd(a,b)},y=y imes frac{c}{gcd(a,b)} ]

求通解

这里我们设之前求出来的通解为 (x_0,y_0)。
设 (d=gcd(a,b))
则通解

(x=x_0+frac{b}{d} imes t,y=y0-frac{a}{d} imes t)

t是任意整数。
为什么是这样呢？
显然我们需要满足

[ax+by=c ]

把 (x,y) 拆开来：

[a(x_0+n)+b(y_0-m)=c ]

于是就有

[an-bm=0 ]

又因为 (n,m) 必须是整数，所以只有上面说的那个可以满足要求了。

求最小正整数解

这里指 (x) 是最小正整数。
当我们求出一组特解后，最小正整数解即

[x=(x_0\%frac{b}{d}+frac{b}{d})\%frac{b}{d},y=(c-ax)/b ]

上面的式子用的是 C++ 语法。
求最小正整数解惯用手法，这里不再累述。