算法：扩展欧几里得

发表于 | 更新于 | 阅读次数：

不定方程新姿势

首先我们明确一下，扩欧可以用来求类$ax+by=c$ 形式的不定方程。

然后对于 $gcd(a,b)$ ，有任何非零系数$t1,t2,t3$ ，满足$t1a+t2b=t3gcd(a,b)$

那么很明显如果$c$ 是$gcd(a,b)$ 的倍数的话，这个方程是肯定有解的

得到这个结论后，我们就可以开始思考怎么得到答案

因为$gcd(a,b)=gcd(b,a\% b) $ 所以我们得到

变形后的式子也是满足gcd的性质的，也就是说我们还可以变形得到

这个式子就是求GCD的式子，也就是说我们可以这样一直递归下去，直到b为0时，y被消去，得解$x=1$

然后递归向上求解的时候，我们就可以又模运算逆向求解得x,y;

即$k=x,x=y,y=k-a/b*y$ 这个就是对于递归下去的时候再向上求出解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void exgcd(int a,int b)
{
	if(!b)
	{
		g=a;
		x=1;
		b=0;
		return ;
	}
	exgcd(b,a%b);
	int k=x;
	x=y;
	y=k-a/b*y;
}