快速求算两数的最大公约数（gcd）

快速求得a和b的最大公约数的主要方式有两种：

• 更相减损法
• 欧几里得算法

其中欧几里得算法的递归实现最为好写，复杂度为O(log(a+b)),在绝大多数的情况下适用，只有在需要实现高精度时，才会考虑使用更相减损法。

还有一种stein算法，三叶大佬说是没有必要掌握的。

以今天的LeetCode每日一题（1447. 最简分数）为例：

class Solution {
	//欧几里得算法(又叫辗转相除法)
	int gcd(int a, int b) {
    	return b == 0? a : gcd(b, a % b);
    }
    public List<String> simplifiedFractions(int n) {
    	List<String> res = new ArrayList<>();
        for (int i = 1; i < n; i++) {
        	for (int j = i + 1; j <= n; j++) {
            	if (gcd(i, j) == 1) res.add(i + "/" + j);
            }
        }
        return res;
    }
}

/**
 *更相减损法
 */
	
    int gcd(int a, int b) {
    	while (true) {
        	if (a > b) a -= b;
            else if (a < b) b -= a;
            else return a;
        }
    }

• 欧几里得算法的结论：gcd(a, b) = gcd(b, a mod b),证明过程可bilibili;递归写法就是反复利用这个结论，直到出现可以整除的两数，较小的数即为两者的最小公约数。
• 更相减损法更容易从名字上直观地理解，每次都是大数减小数，直到两数相同为止，此时的数值即为所求的最小公约数。