NC151 最大公约数

发表于 更新于 分类于 ， ， Waline： 本文字数： 2k 阅读时长 ≈ 2 分钟

NC151 最大公约数

描述

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

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

数据范围：$1\leq a,b\leq10^9$

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

示例1

输入：

1
3,6

返回值：

1
3

示例2

输入：

1
8,12

返回值：

1
4

备注：

a和b的范围是[1-109]

关联企业

我的解析

使用辗转相除法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import java.util.*;

public class Solution {
    /**
    * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    *
    * 求出a、b的最大公约数。
    * @param a int 
    * @param b int 
    * @return int
    */
    public int gcd (int a, int b) {
        // 辗转相除法求最大公约数
        // 保证a>=b
        if(a<b){
            a^=b;
            b^=a;
            a^=b;
        }
        // 求余数
        int yushu=a%b;
        // 如果余数为0,那么商就是最大公约数
        if(yushu==0){
            return b;
        }
        else {
            // 转换成求商和余数的最大公约数
            return gcd(b,yushu);
        }
    }
}

使用辗转相减法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 求出a、b的最大公约数。
     * @param a int 
     * @param b int 
     * @return int
     */
    public int gcd (int a, int b) {
        // 辗转相减法求最大公约数
        while (a != b) {
            if (a > b)
                a = a - b;
            else
                b = b - a;
        }
        return a;
    }
}

精华题解

更相减损法

这个思想起源于我国古代的《九章算术》，它原本是为约分而设计的，但它适用于任何需要求最大公约数的场合。原文是这么描述的：“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。”

翻译成白话将就是：

第一步：对于任意给定的两个正整数a、b，要求出他们的最大公约数，首先判断他们俩是否都是偶数（能被2整除），如果都是偶数则一直除以2约简，直至不能再被2整除:

1
2
3
4
while(a%2==0 && b%2==0){
    a = a/2;
    b = b/2;
}

第二步：如果不是，那么就执行下一步，即用较大的数减去较小的数，然后将所得的差值赋值给原先拥有较大值的那个变量，再拿这个变量与较小值的那个变量进行比较，继续用二者中较大的减去较小的，直到两个变量相等；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int gcd (int a, int b) {
    // write code here
    if (a % b == 0 || b % a == 0){
        return a % b == 0 ? b : a;
    }
 
    while(a != b){
        if(a > b){
            a = a - b;
        } else {
            b = b - a;
        }
    }
    return a;
}

辗转相除法

1
2
3
4
5
6
7
8
9
import java.util.*;
public class Solution {
    public int gcd (int a, int b) {
        if(a%b==0)
            return b;
        else
            return gcd(b,a%b);
    }
}

网络题解

https://www.cnblogs.com/HuangWj/p/11261870.html

大数减小数，直到两数相等时，即为最大公约数。

递归实现

1
2
3
4
5
6
7
8
9
10
// 辗转相减法，递归实现
int GCD(int a, int b)
{
    if (a == b)
        return a;
    else if (a > b)
        return GCD(a,b);
    else
        return GCD(b,a);
}

迭代实现

1
2
3
4
5
6
7
8
9
10
// 辗转相减法，迭代实现
int GCD(int a, int b)
{
    while(a == b)
    {
        if (a > b) a -= b;
        else b -= a;
    }
    return a;
}

文章2

https://blog.csdn.net/Holmofy/article/details/76401074