求最大公约数函数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;
}

小结

最大公约数是一类非常基础的算法问题，在我们实际编程中也经常会用到，如求最小公倍数，化简分数等。这里我们介绍了两种求最大公约数的方法，分别是辗转相除法和欧几里得算法，在实际应用中可以根据需要选择不同的方法进行求解。同时，我们还看到了求解线性同余方程的应用。