求最大公約數函數gcd

在計算機編程中，求最大公約數是一件很常見的事情。最大公約數是指兩個或多個整數共有約數中，最大的一個數。而求最大公約數的函數gcd也成為編程中的常用演算法之一。

一、gcd函數的定義與基本思路

int gcd(int a, int b) {
    while (b != 0) {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

上述代碼實現了求a和b的最大公約數的函數gcd。其基本思路是不斷地將a,b作為除數，r= a % b的餘數作為除數，直到b變成0，此時a就是最大公約數。

當然，上述代碼也可以寫為遞歸形式：

int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

兩種寫法其實是原理相同，只是實現方式不同而已。

二、優化演算法

前面的演算法定義簡潔，思路明晰，但是卻存在一個慢的問題。

我們看一下，比如求100和87的最大公約數，這裡大家可以手算一下，結果是1。而如果用前面的演算法來求，需要循環100次（即b從1到100），才能得到最後的結果。當然，這只是比較複雜情況下的一種極端情況。但是可想而知，若要計算更大數值的最大公約數，則這種循環演算法需要的時間將更長。

這時我們可以用更高效率的輾轉相除演算法——歐幾里得演算法。

歐幾里得演算法是基於這樣一條性質：兩個整數的最大公約數等於其中較小的數和兩數相除餘數的最大公約數。

比如如下的例子，用輾轉相除法求最大公約數：

gcd(319,377)=gcd(319,58)=gcd(49,58)=gcd(49,9)=gcd(4,9)=gcd(4,1)=4

這裡的思路是不斷把較大的那個數減去較小的數，直到兩者相等，那麼這個數就是最大公約數。

有了這個演算法，代碼實現起來就非常簡單了。

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

三、gcd函數的應用

除了求最大公約數以外，gcd函數還有很多應用，下面我們列舉幾個典型的。

1. 最小公倍數

最小公倍數定義為兩個或多個整數公有的倍數中，最小的一個整數。最小公倍數等於兩個整數的乘積除以它們的最大公約數。

int lcm(int a, int b) {
    return a * b / gcd(a, b);
}

2. 分數的化簡

在一些涉及到分數情況下，我們需要把分式化簡為最簡形式。對於一個分數a/b，其最簡形式即分子分母沒有其他公因數存在。那麼，我們只需要調用求a和b的最大公約數函數，然後分子和分母同除以最大公約數即可。

int fenzi,fenmu;//定義分子和分母
int gcd_value = gcd(fenzi,fenmu);//求最大公約數
fenzi /=gcd_value;//分子除以最大公約數
fenmu /=gcd_value;//分母除以最大公約數

3. 求解線性同餘方程

線性同餘方程是指形如ax ≡ b(mod m)的方程，其中a、x、b、m均為整數。

一個典型的應用是求解模線性方程ax + by = c 的解(x,y)。

其中，c是常數，a、b是整數（a,b同樣也是線性同餘方程的係數），x、y是整數解。

解法是首先求出a、b的最大公約數，如果c不是其的倍數則無整數解，否則用擴展歐幾里得演算法求得x、y的一組通解，在此基礎上計算出特解。

bool solve(int a, int b, int c, int &x,int &y){
    int d=gcd(a,b);
    if(c%d) return false;
    x=y=0;
    if(d==a){
        x=c/d;
        return true;
    } 
    if(d==b){
        y=c/d;
        return true;
    }
    int k=c/d;
    if(solve(b, a%d, c%d, x, y)){
        x+=k;
        swap(x,y);
        return true;
    }
    return false;
}

小結

最大公約數是一類非常基礎的演算法問題，在我們實際編程中也經常會用到，如求最小公倍數，化簡分數等。這裡我們介紹了兩種求最大公約數的方法，分別是輾轉相除法和歐幾里得演算法，在實際應用中可以根據需要選擇不同的方法進行求解。同時，我們還看到了求解線性同餘方程的應用。