一、定義

如果有一個自然數a能被自然數b整除，則稱a為b的倍數，b為a的約數。幾個自然數公有的約數，叫做這幾個自然數的公約數。公約數中最大的一個公約數，稱為這幾個自然數的最大公約數。

二、性質

重要性質：

gcd(a,b)=gcd(b,a) （交換律）

gcd(-a,b)=gcd(a,b)

gcd(a,a)=|a|

gcd(a,0)=|a|

gcd(a,1)=1

gcd(a,b)=gcd(b, a mod b)

gcd(a,b)=gcd(b, a-b)

如果有附加的一個自然數m,

則: gcd(ma,mb)=m * gcd(a,b) (分配律)

gcd(a+mb ,b)=gcd(a,b)

如果m是a和b的最大公約數，

則： gcd(a/m ,b/m)=gcd(a,b)/m

在乘法函數中有：

gcd(ab,m)=gcd(a,m) * gcd(b,m)

兩個整數的最大公約數主要有兩種尋找方法：

* 兩數各分解質因數，然后取出同樣有的質因數乘起來

*輾轉相除法（擴展版）

和最小公倍數（lcm）的關系：

gcd(a, b) * lcm(a, b) = ab

a與b有最大公約數，

兩個整數的最大公因子可用于計算兩數的最小公倍數，或分數化簡成最簡分數。

兩個整數的最大公因子和最小公倍數中存在分配律：

* gcd(a, lcm(b, c)) = lcm(gcd(a, b), gcd(a, c))

* lcm(a, gcd(b, c)) = gcd(lcm(a, b), lcm(a, c))

在坐標里，將點(0, 0)和(a, b)連起來，通過整數坐標的點的數目（除了(0, 0)一點之外）就是gcd(a, b)。

三、求法

1、輾轉相除法(歐幾里德算法)

兩個數的最大公約數是指能同時整除它們的最大正整數。

設兩數為a、b(a≥b)，求a和b最大公約數??的步驟如下：

(1)用a除以b(a≥b)，得 a /b = q...r1(0<=r1) 。

(2)若 r1 =0 ，則(a,b)=b??；

(3)若 r1 !=0 ，則再用b除以??r1，得 b /r1= q...r2 (0<r2).

(4)若 r2=0 ，則 (a,b)=r1 ；若 r2!=0 ，則繼續用 r1 除以r2??，......，如此下去，直到能整除為止。

其最后一個余數為0的除數即為(a,b)的最大公約數。

算法描述

用輾轉相除法確定兩個正整數 a 和 b(a≥b) 的最大公因數 gcd(a,b) ：

當 a mod b =0??時，gcd(a,b) = gcd(b,a mod b)??；否則 gcd(a,b) = gcd(b, a mod b) 遞歸或循環運算得出結果。

代碼：

C++版本一

int gcd(int a,int b) { // 約數和倍數不包含0，則遇到0情況則直接排除if(0==a||0==b)return 0;int t=a%b;while(t){a=b;b=t;t=a%b;}return b; }

?C++版本二

int Gcd(int m, int n) //輾轉相除法，求最大公約數 {return m == 0 ? n : Gcd(n % m, m); }int Lcm(int m, int n) //最小公倍數 {return (m * n / Gcd(m, n)); }

C++版本三

ll GCD(ll a,ll b){while(b^=a^=b^=a%=b);return a;}

?

2、Stein算法

由J. Stein 1961年提出的Stein算法很好的解決了歐幾里德算法中的這個缺陷，Stein算法只有整數的移位和加減法，為了說明Stein算法的正確性，首先必須注意到以下結論：

gcd(a,a)=a，也就是一個數和其自身的公約數仍是其自身。

gcd(ka,kb)=k gcd(a,b)，也就是最大公約數運算和倍乘運算可以交換。特殊地，當k=2時，說明兩個偶數的最大公約數必然能被2整除。

當k與b互為質數，gcd(ka,b)=gcd(a,b)，也就是約掉兩個數中只有其中一個含有的因子不影響最大公約數。特殊地，當k=2時，說明計算一個偶數和一個奇數的最大公約數時，可以先將偶數除以2

算法步驟

1、如果An=Bn,那么An(或Bn)*Cn是最大公約數,算法結束

2、如果An=0，Bn是最大公約數，算法結束

3、如果Bn=0，An是最大公約數，算法結束

4、設置A1=A、B1=B和C1=1

5、如果An和Bn都是偶數，則An+1=An/2，Bn+1=Bn/2，Cn+1=Cn*2(注意，乘2只要把整數左移一位即可，除2只要把整數右移一位即可)

6、如果An是偶數，Bn不是偶數，則An+1=An/2，Bn+1=Bn，Cn+1=Cn(很顯然啦，2不是奇數的約數)

7、如果Bn是偶數，An不是偶數，則Bn+1=Bn/2，An+1=An，Cn+1=Cn(很顯然啦，2不是奇數的約數)

8、如果An和Bn都不是偶數，則An+1=|An-Bn|/2，Bn+1=min(An,Bn)，Cn+1=Cn

9、n加1，轉1

代碼：

int gcd(int a ,int b) {if(a < b){//arrange so that a>bint temp = a;a = b;b=temp;}if(0 == b)//the base casereturn a;if(a % 2 == 0 && b % 2 == 0)//a and b are evenreturn 2 * gcd(a / 2, b / 2);if ( a % 2 == 0)// only a is evenreturn gcd(a / 2, b);if ( b % 2 == 0 )// only b is evenreturn gcd(a, b / 2);return gcd((a + b) / 2, (a -b ) / 2);// a and b are odd }

?

3、分解質因數

四、例題

http://oj.acm.zstu.edu.cn/JudgeOnline/problem.php?cid=3703&pid=9（題解：https://blog.csdn.net/weixin_43272781/article/details/82899925）

五、參考文章

https://blog.csdn.net/niushuai666/article/details/6607707

https://blog.csdn.net/C_acgl/article/details/82528192

https://blog.csdn.net/aime521/article/details/51891907

總結

以上是生活随笔為你收集整理的最大公约数(Greatest_Common_Divisor)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。