1.歐幾里得算法

歐幾里得是求最大公約數(shù)的經(jīng)典算法，又稱輾轉(zhuǎn)相除法。
gcd函數(shù)就是用來求(a,b)的最大公約數(shù)的。
gcd函數(shù)的基本性質(zhì)：
gcd(a,b)=gcd(b,a)=gcd(-a,b)=gcd(|a|,|b|)
gcd(a,b)=gcd(b,a mod b)

證明：a可以表示成a = kb + r，則r = a mod b假設(shè)d是a,b的一個公約數(shù)，則有 d | a , d | b ，而r = a - kb，因此 d | r 因此d是(b,a mod b)的公約數(shù)假設(shè)d 是(b,a mod b)的公約數(shù)，則 d | b , d | r ，但是a = kb +r因此d也是(a,b)的公約數(shù)因此(a,b)和(b,a mod b)的公約數(shù)是一樣的，其最大公約數(shù)也必然相等，得證

所以通過遞歸，最終可以使得其中一個參數(shù)為零，則另一個不為零的數(shù)則為最大公約數(shù)
板子如下：

typedef long long ll; ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b); }

當(dāng)然也可以求最小公倍數(shù)
最小公倍數(shù)lcm=a * b/gcd(a,b)

2.擴(kuò)展算法

1.解ax+by=gcd(a,b)

對于不完全為 0 的非負(fù)整數(shù) a，b，gcd(a,b)表示 a，b 的最大公約數(shù)，必然
存在整數(shù)對 x，y ，使得 gcd（a，b）=ax+by。

求解 x，y的方法的理解:設(shè) a>b。 1，顯然當(dāng) b=0，gcd（a，b）=a。此時 x=1，y=0； 2，a>b>0 時:設(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; 說明： a-[a/b]*b即為mod運(yùn)算。[a/b]代表取小于a/b的最大整數(shù)。 也就是ax1+ by1 == ay2+ b(x2- [a / b] *y2); 根據(jù)恒等定理得:x1=y2;y1=x2- [a / b] *y2; 這樣我們就得到了求解 x1,y1 的方法：x1，y1 的值基于 x2，y2. 上面的思想是以遞歸定義的，因?yàn)?gcd 不斷的遞歸求解一定會有個時候 b=0，所以遞歸可以結(jié)束。

板子如下：

int gcd(int a,int b,int &x,int &y){if (b==0){x=1,y=0;return a;}int q=gcd(b,a%b,y,x);y-=a/b*x;return q; }

可以這樣思考:
對于a’=b,b’=a%b 而言，我們求得 x, y使得 a’x+b’y=Gcd(a’,b’)
由于b’=a % b=a - a / b * b
(這里的 / 是程序設(shè)計(jì)語言中的除法)
那么可以得到:
ax+by=gcd(a,b) =>
bx+(a - a / b * b)y = gcd(a’, b’) = gcd(a, b) =>
ay +b(x - a / b * y) = Gcd(a, b)
因此對于a和b而言，他們的相對應(yīng)的p，q分別是 y和 (x-a/b*y)。
板子如下：

nt gcd(int a,int b,int &x,int &y){if (b==0){x=1,y=0;return a;}int q=gcd(b,a%b,x,y);int t=x;x=y;y=t-a/b*y;return q; }

2.解ax+by=c

使用擴(kuò)展歐幾里德算法解決不定方程的辦法
對于不定整數(shù)方程pa+qb=c，若 c mod Gcd(a, b)=0,則該方程存在整數(shù)解，
否則不存在整數(shù)解。
通過上面的程序即可求出一組x，y使得gcd（a，b）=ax+by
找其所有解的方法如下：
在找到x * a+y * b = Gcd(a, b)的一組解x0,y0后，
可以得到x * a+y * b = c的一組解:
x1 = x0 * (c/Gcd(a,b)),
y1 = y0 * (c/Gcd(a,b))，

3.解集

假設(shè)我們得出ax+by=c一組解x與y，如果x每減去一個t（t為常數(shù)），
那么y至少必須加上一個a’* t/b’
(其中a’=a/gcd(a,b)，b’=b/gcd(a,b))，
才能使等式兩邊成立,即
　　a(x-t)+b(y+a’ * t/b’)=ax+by=c
由于我們需要變換后的x和y仍然是整數(shù)，由于t已經(jīng)是整數(shù)，即x-t也一定是整數(shù)，
現(xiàn)在只需考慮a’ * t/b’是否為整數(shù)，由于gcd(a’,b’)=1，
即a’一定不是b’的倍數(shù)，故必須令t=t * b’(即c必須是b’的倍數(shù))，才使得a’ * t/b’為整數(shù)，即解集為：
　　x=x-t * b/gcd(a,b)，y=y+t * a/gcd(a,b)，t為任意整數(shù)
特別的，當(dāng)gcd(a,b)=1，解集為：x=x-t * b，y=y+t * a

練習(xí)

1.擴(kuò)展gcd-時間復(fù)雜性

題目內(nèi)容： 計(jì)算循環(huán)語句的執(zhí)行頻次 for(i=A; i!=B ; i+=C) x+=1; 其中A,B,C,i都是k位無符號整數(shù)。輸入描述A B C k, 其中0<k<32輸出描述輸出執(zhí)行頻次數(shù)，如果是無窮，則輸出“forever”輸入樣例3 7 2 16輸出樣例2

k位無符號整數(shù)則數(shù)據(jù)范圍為0~2^k(具體含義可以搜索無符號整數(shù)溢出)
所以設(shè)y，題目意思可以理解為
A+x * C - B=y * 2^k => x * C+y * 2^k=B-A
于是可以用exgcd求解
令a=C，b=2^k，c=B-A
首先判斷B-A 是否是gcd(a,b)倍數(shù)，如果不是則無法求出一組x。
求出一組x0，y0后，則通解為
x=x0 * a/gcd(a,b)*t
y=y0 - b/gcd(a,b)*t
令n=a/gcd(a,b),m= b/gcd(a,b)
則可以得到
①x0 * a+y0 * b=c
②a(x0+n * t)+b(y0-m * t)=c
聯(lián)立上式
可得
a * t * n - b * t * m = 0
a * n - b * m=0
也就是a * n=b * m，要想n,m最小就是使得a * n，b * m都為a，b的最小公倍數(shù)：
a * n = (a * b)/gcd(a,b) => n = b/gcd(a,b);
同理：m = a /gcd(a,b);
則：
x0 = (x % n + n)%n
y0 = (y % m + m)%m

#include<iostream> using namespace std; //A + xC - B = y * 2^k int exgcd(int a,int b,int &x,int &y){if(b==0){x=1;y=0;return a;}int d=exgcd(b,a%b,x,y);int t=x;x=y;y=t-a/b*y;return d; } int main(){int A,B,C,k;cin >> A >> B >> C >> k;//特判A=B=C=K=0 if(A==0&&A==B&&B==C&&C==k) return !(cout << "forever");int b=1<<k,a=C,c=B-A,x=10,y=10;int d=exgcd(a,b,x,y);if(c%d){return !(cout << "forever");} x=(x*(c/d))%b;x=(x%(b/d)+(b/d))%(b/d);//防止出現(xiàn)負(fù)數(shù)解cout << x;return 0; }

總結(jié)

以上是生活随笔為你收集整理的gcd算法以及exgcd的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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