扩展欧几里得算法

2020年3月25日 · 11 views · 

扩展欧几里得算法是用来求对于已知的a,b,求 $ax+by=gcd(a,b)$ 的一组解的算法。

首先,试着用辗转相除法来求22和60的最大公因数。

可以从①中看到,gcd(a,b)=2。接着,把每一步的式子换一种表示方式(如图②)。用a表示60,b表示22。从上往下看,每一步的余数都可以用a和b来表示。例如:$16=a-2×b,6=b-1×16=b-(a-2×b)$。那么如果一路往下做,最后的gcd(a,b)=2也可以用a、b来表示!如果能求得如何用a,b来表示gcd(a,b),就可以解出ax+by=gcd(a,b)!

用r表示计算所得的余数,r’表示上一次计算的,r”表示上两次计算的,k表示商。则有:$$r=r′′−k×r′$$

由于要求如何用a,b表示r,也就是求ax+by=r3的x,y,所以用两个变量记录a,b的系数x,y,每次只要改变x,y即可。因此可以写出如下函数:

void exgcd(int a, int b, int& x, int& y)
{
	int a1 = 0, b1 = 1, a2 = 1, b2 = 0;
	while (a%b!=0)
	{
		int k = a / b;
		x = a2 - k*a1;
		y = b2 - k * b1;
		a2 = a1, a1 = x, b2 = b1, b1 = y;
		int r = a % b;
		a = b;
		b = r;
	}
}

由于ax+by=gcd(a,b)是一个不定方程,所以它有无数组解。那么如何通过一组解求得其它解呢?

设g=gcd(a,b)。则可以得到当k取任何值得时候,$$\left(x,y\right)\rightarrow\left(x+k\times\frac{b}{g}\ ,\ y-k\times\frac{a}{g}\right)$$

因为把它带入ax+by,后面部分互相抵消,最后还是剩下ax+by。为什么要除以g?因为a和b并不互质,如果不除以g会漏掉一些解。

返回

Steven's Website Copyright © 2020 Steven
Powerd by Wordpress & Theme by Steven
粤ICP备20028373号