首先要知道gcd函數(shù)的基本性質(zhì):
gcd(a,b)=gcd(b,a)=gcd(|a|,|b|)=gcd(b,a%b)//已通過代碼驗(yàn)
不知道輾轉(zhuǎn)相除法的請(qǐng)點(diǎn)這里
擴(kuò)展歐幾里得算法:
對(duì)于不完全為 0 的非負(fù)整數(shù) a巷怜，b腾夯，gcd（a旋炒，b）表示 a呻拌，b 的最大公約數(shù)洗搂，必然
存在整數(shù)對(duì) x烤咧，y 腹暖，使得 k*gcd（a，b）=ax+by铡恕。
代碼如下:
int exGcd(int a,int b,int &x,int &y)//求出來的x,y就是這么多了.相當(dāng)于全局變量
{
if(b==0)
{
x=1;y=0;
return a;
}
int r=exGcd(b,a%b,x,y);
int t=x;x=y;y=t-a/b*y;
return r;//r為a,b的最大公約數(shù).
}
對(duì)以上代碼的一些解釋.
設(shè) a>b琢感。
1，顯然當(dāng) b=0探熔，gcd（a驹针，b）=a。此時(shí) x=1诀艰，y=0柬甥；
2墙牌，a>b>0 時(shí)
設(shè) ax1+ by1= gcd(a,b);
bx2+ (a mod b)y2= gcd(b,a mod b);
根據(jù)樸素的歐幾里德原理有 gcd(a,b) = gcd(b,a mod b);
則:ax1+ by1= bx2+ (a mod b)y2;
即:ax1+ by1= bx2+ (a - [a / b] * b)y2=ay2+ bx2- [a / b] * by2;
也就是ax1+ by1 == ay2+ b(x2- [a / b] *y2);
根據(jù)恒等定理得：x1=y2; y1=x2- [a / b] y2;
這樣我們就得到了求解 x1,y1 的方法：x1，y1 的值基于 x2暗甥，y2.
(因?yàn)閤2,y2就是第一個(gè)遞歸來的,所以就可以根據(jù)遞歸來求出x1,x2).
上面的思想是以遞歸定義的，因?yàn)?gcd 不斷的遞歸求解一定會(huì)有個(gè)時(shí)候 b=0捉捅，所以遞歸可以結(jié)束撤防。
擴(kuò)展歐幾里德算法
擴(kuò)展歐幾里德算法是用來在已知a, b求解一組x，y使得ax+by = kgcd(a, b) =d(解一定存在棒口，根據(jù)數(shù)論中的相關(guān)定理)(即解一定存在,且答案為gcd(a,b)的整數(shù)倍)(所以下次看到要馬上想到啊!!!)
//求出來的x是滿足方程最小的那個(gè)x,所以有可能為負(fù)數(shù),轉(zhuǎn)換成滿足方程的最小正數(shù)的方法是(x%a+a)%a,所以要根據(jù)題意來不斷變換.
這個(gè)算法主要用于求//說實(shí)話,這個(gè)遇到題還真不好分析,真的只有多做題,提高自己的知識(shí),再去做吧.
1:求解不定式
2:求解模線性方程(線性同余方程)
3:求解模的逆元
這里對(duì)求解不定式再做一定的說明,所有的我們都轉(zhuǎn)換成求ax+by=gcd(a,b),然后再根據(jù)題意在方程的兩邊同時(shí)乘一定的數(shù)從而轉(zhuǎn)換成我們要求的那個(gè)方程.然后考慮下x的正負(fù)就可以了.
具體操作步驟請(qǐng)看水題poj1061
