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

个人主页：清风莫追
系列专栏：牛客刷题——数据结构与算法

---

1. 题目

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

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

数据范围： $1\le a,b\le 10^9$

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

2. 算法设计思路

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

为什么要从 min 开始递减，而不是从 1 开始递增呢？想一想：我们要求的是最大公约数。
思路二：辗转相除法
gcd()为求最大公约数的函数
反复使用：$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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

思路二代码：

int gcd(int a, int b ) {
    if(b == 0){
        return a;
    }
    return gcd(b, a%b);
}
1
2
3
4
5
6

.

4. 运行结果

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

---

CSDN话题挑战赛第2期
参赛话题：学习笔记

感谢阅读