本篇將附上擴(kuò)展歐幾里得算法的思想與推導(dǎo);

---

對(duì)于一個(gè)方程(a*x+b*y=gcd(a,b))來(lái)說(shuō),我們可以做如下的推導(dǎo):

設(shè)有(a*x_1+b*y_1=gcd(a,b));

同時(shí)我們有(b*x_2+(a\%b)*y_2=gcd(b,a\%b));

對(duì)于這個(gè)方程組,我們希望知道的是(x_1,x_2,y_1,y_2)之間的關(guān)系,這樣我們才可以遞歸解決這個(gè)問(wèn)題

我們觀察(b*x_2+(a\%b)*y_2)這個(gè)式子,我們可以將((a\%b))寫(xiě)作((a-lfloorfrac{a}{b}floor*b)),將括號(hào)打開(kāi)常數(shù)(a,b)合并,合并之后的結(jié)果為(a*y_2+b*(x_2-lfloorfrac{a}{b}floor*y_2)))

由于歐幾里得算法的原理(gcd(a,b)==gcd(b,a\%b)),我們將兩式子聯(lián)立,對(duì)比系數(shù)即可得到(x_1=y_2,y_1=x_2-lfloorfrac{a}{b}floor*y_2)

這個(gè)遞歸的邊界是什么呢?我們知道,當(dāng)樸素歐幾里得到達(dá)邊界時(shí),(return gcd(a,0)=a),那么邊界條件就是對(duì)(a*x_0+b*y_0=a)求解,很顯然,此時(shí)(x_0=1,y_0=0)

當(dāng)我們遞歸求出了一個(gè)方程的特解時(shí),如何求出這個(gè)方程的通解呢?

方程(a*x+b*y=gcd(a,b))中,如果將x加上一個(gè)常數(shù)(k_1,y)減去一個(gè)常數(shù)(k_2),仍然保持原方程成立,那么(x+k_1,y-k_2)就是方程的一個(gè)新解,這個(gè)k應(yīng)該如何選擇呢?

實(shí)際上很簡(jiǎn)單,(a*(x+k_1)+b*(y+k_2)=gcd(a,b)),打開(kāi)括號(hào),(a*x+a*k_1+b*y-b*k_2=gcd(a,b));

我們保證原方程成立,就需要(a*k_1==b*k_2),那么顯然(k_1=b,k_2=a)是一種合理的情況,但是這樣是無(wú)法包含所有整數(shù)解的,因?yàn)槲覀兗由系倪@個(gè)值并非是最小值

那我們應(yīng)該加上什么值才行呢?我們發(fā)現(xiàn)當(dāng)(a*k_1==b*k_2=t*lcm(a,b))可以保證得到所有解,于是每次尋找解就可以分別在(x)加上(frac{b}{gcd(a,b)},在y減去frac{a}{gcd(a,b)})就可以了

對(duì)于方程(a*x+b*y=c)我們又該如何求解?我們發(fā)現(xiàn)如果((c\%gcd(a,b)!=0))那么這個(gè)方程是無(wú)解的,而如果(gcd(a,b)*t==c),我們就可以按上面的方法求解之后對(duì)我們的解乘上一個(gè)(t(t=frac{c}{gcd(a,b)}))

(code:)

int exgcd(int a,int b,int &x1,int &y1)
{
	if(!b)
	{
		x1=1,y1=0;
		return a;
	}
	int x2,y2;
	int d=exgcd(b,a%b,x2,y2);
	x1=y2,y1=x2-(a/b)*y2;
	return d;
}

總結(jié)

以上是生活随笔為你收集整理的扩展欧几里得算法详解的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。