Greatest Common Divisor

题目地址：

https://www.lintcode.com/problem/greatest-common-divisor/description

求两个正整数的最大公约数。

思路是辗转相除法。代码如下：

public class Solution {
    /**
     * @param a: the given number
     * @param b: another number
     * @return: the greatest common divisor of two numbers
     */
    public int gcd(int a, int b) {
        // write your code here
        if (a * b == 0) {
            return a + b;
        }
        
        while (b != 0) {
            int tmp = a % b;
            a = b;
            b = tmp;
        }
        
        return a;
    }
    
    public static void main(String[] args) {
        System.out.println(new Solution().gcd(10, 15));
    }
}

时间复杂度$O(\log \max \{a,b\})$（原因是$(a,b)$的减少速度一定至少快于斐波那契数列，而斐波那契数列的增长速度是指数级的），空间$O(1)$。

本文地址：https://blog.csdn.net/qq_46105170/article/details/110228209