题解|NC151最大公约数

最大公约数

如果有一个自然数 能被自然数 整除，则称 为 的倍数， 为 的约数。几个自然数公有的约数，叫做这几个自然数的公约数。公约数中最大的一个公约数，称为这几个自然数的最大公约数。
输入 和 , 请返回 和 的最大公约数。

解法一：暴力做法

设两个数中较大的数为 ，较小的数为 。循环暴力求解， 从 开始循环，到 停止，判断当前 是否能同时整除和，如果可以，退出循环。
时间复杂度：，空间复杂度:。

解法二：辗转相除法

辗转相除法大致过程是这样的：用两个数中较大的数除以较小的数，如果能整除，那么较小的数就是所求的最大公约数。如果不能整除，使用余数来除刚才的除数；再用这新除法的余数去除刚才的余数。直到一个除法能够整除，这时作为除数的数就是所求的最大公约数。
例如找36和54的最大公约数，如图所示，。 作为余数，参与到下一次除法运算中，而 ，余数为0。这时被用作除数的 就是所求的最大公约数。

证明

设为第次相除的余数，共进行 次除法运算， 为最大公约数，我们现在要证明 与 相等。

首先证明 可以同时整除 和 ：

易知是，所以有

1. （ 可以整除 )
2. （ 可以整除 )
   ...
   同理可得 可以整除之前所有步骤的余数。
   因此它是一个公约数，所以必然小于或者等于最大公约数 。

然后证明最大公约数可以整除。

易知 为 和 的倍数，写成 ，
由于 ，所以 整除 。同理可证 整除每个余数,包括 ，得到。

由1和2可知，与相等。

时间复杂度： 空间复杂度: 。

代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 求出a、b的最大公约数。
     * @param a int 
     * @param b int 
     * @return int
     */
    int gcd(int a, int b) {
        // write code here
        int tmp;
        while(b != 0){
            tmp = a % b;
            a = b;
            b = tmp;
        }
        return a;
    }
};