【概念】

1.公約數：有 k 個非零整數?，若?，s.t.?，則稱 d 為??的公約數。

2.最大公約數：公約數中最大的一個數稱為最大公約數，記為：

注：

? ① 最大公約數一定是存在的，其最小值為 1。

? ② 當 GCD=1 時，則稱這些數是互質的。

? ③ 公約數一定是最大公約數的約數。

3.公倍數：有 k 個非零整數?，若?，s.t.?，則稱 d 為??的公倍數。

4.最小公倍數：公倍數中最小的一個數稱為最小公倍數，記為：

注：公倍數一定是最小公倍數的倍數。

【歐幾里德算法】

歐幾里德算法又稱為輾轉相除法，用于求兩個數的最大公約數，其原理為：，即：

1.實現

int GCD(int x,int y){if(y==0)return x;elsereturn GCD(y,x%y); }

2.二進制算法

1）原理

為提高效率，可將歐幾里德算法進行優化，通過不斷去除因子 2 來降低常數。

• 當 時，
• 當 x、y 均為偶數時，
• 當 x 為偶數，y 為奇數時，
• 當 x 為奇數，x 為偶數時，

2）實現

int GCD(int x,int y){if(x==0)return y;if(y==0)return x;int i,j;for(i=0;!(x&1);i++)//約去2x>>=1;for(j=0;!(y&1);j++)//約去2y>>=1;if(i>j)i=j;while(true){if(x<y){//若x<y，交換兩數，保證大數在前x^=y;y^=x;x^=y;}if((x-=y)==0)//輾轉減return y<<i;while(!(x&1))//約去2x>>=1;} }

【擴展歐幾里德算法】

擴展歐幾里德算法是在已知 x、y?時，求解一組 a、b，使得

1.過程分析

設

① 當 時，，此時?

② 當 x>y>0 時

? ? ?設 ，

? ? ?由于?

? ? ?故?

? ? ?即?

? ? ?因此?

? ? ?易得??

這樣就得到了求解 、?的方法：、 的值基于 、

由于 GCD?不斷的遞歸求解，因此一定會在某時?，結束遞歸，從而得出 a、b 的值。

注：?x-[x/y]*y 即為 mod 運算，[x/y] 代表取小于 x/y 的最大整數。

2.實現

int Extended_GCD(int x,int y,int &a,int &b){if(y==0){a=1;b=0;return x;}int gcd=Extended_GCD(b,a%b,y,x);b-=a*(x/y);return gcd; } int main(){//形如 ax+by=GCD(x,y)int x,y,a,b;cin>>x>>y;int gcd=Extended_GCD(x,y,a,b);cout<<"GCD="<<gcd<<endl;cout<<"a="<<a<<",b="<<b<<endl;return 0; }

【最小公倍數】

定理：a、b 兩個數的最小公倍數乘以它們的最大公約數等于 a 和 b 本身的乘積。

即：

在求 LCM 時，如果將 LCM 寫成 a*b/GCD(a,b)，a*b 可能會溢出，正確的方法應該是先除后乘，即：a/GCD(a,b)*b

int GCD(int x,int y){return !y?x:GCD(y,x%y); } int LCM(int x,int y){return x/GCD(x,y)*y; }

【例題】

取石子游戲（信息學奧賽一本通-T1218）(歐幾里得)：點擊這里

青蛙的約會（POJ-1061）(擴展歐幾里得)：點擊這里
同題：青蛙的約會（洛谷-P1516）：點擊這里

最大公約數和最小公倍數問題（洛谷-P1029）(LCM)：點擊這里

LCM Walk（HDU-5584）(LCM+逆推)：點擊這里

Happy 2006（POJ-2773）(擴展歐幾里得求互素的數)：點擊這里

LCM Challenge（CF-236C）(三個數的最大的LCM)：點擊這里

Faraway（HDU-6639）(思維+LCM)：點擊這里

總結

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

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