【牛客刷题-算法】NC151 最大公约数

1. 题目

描述

如果有一个自然数 a 能被自然数 b 整除，则称 a 为 b 的倍数， b 为 a 的约数。几个自然数公有的约数，叫做这几个自然数的公约数。公约数中最大的一个公约数，称为这几个自然数的最大公约数。

输入 a 和 b , 请返回 a 和 b 的最大公约数。

数据范围： 1 ≤ a , b ≤ 1 0 9 1 \le a,b \le 10^91≤a,b≤10

9

进阶： 空间复杂度 O(1)O(1)，时间复杂度 O(logn)O(logn)

2. 算法设计思路

思路一：简单暴力法

我们只需要先比较a和b，将较小的那个值记为min。然后从min开始，逐个整数递减尝试，如果尝试到 i 时可以同时整除a和b，则停止尝试，并返回 i 值。

为什么要从 min 开始递减，而不是从 1 开始递增呢？想一想：我们要求的是最大公约数。

思路二：辗转相除法

gcd()为求最大公约数的函数

反复使用：g c d ( a , b ) < = > g c d ( b , a % b ) gcd(a,b)<=>gcd(b,a\%b)gcd(a,b)<=>gcd(b,a%b)

这里我们不做数学上的证明，有兴趣可以自行网络搜索证明过程。

3. 代码实现

注：这里并不是完整代码，而只是核心代码的模式
思路一代码：
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 求出a、b的最大公约数。
 * @param a int 
 * @param b int 
 * @return int
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
int gcd(int a, int b ) {
    int min = a > b ? b : a;
    for(int i = min; i > 0; i--){
        if(a % i == 0 && b % i == 0){
            return i;
        }
    }
    return -1;
}

思路二代码：

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

4. 运行结果

成功通过啦！而且可以看到，即使我思路二采用的是递归的写法，运行的效率仍然要高很多。

结束语：

今天的分享就到这里啦，快来加入刷题大军叭！