题解 | #最大公约数#

求最大公约数
1、辗转相除法
gcd(a,b)=gcd(b,a%b)
若要求（a,b)的公约数等于（a,a%b）的公约数，当a%b==0时，b为最大公约数；

class Solution {
public:
    int gcd(int a, int b) {
        if(a%b==0){return b;}
        else{return gcd(b,a%b);}
    }
};

2、更相减损法
性质：两个数的最大公约数等于两个数中较小的和两数之差的最大公约数。

class Solution {
public:
    int gcd(int a, int b) {
        int temp = abs(a - b); //取差的绝对值 
        while(temp != 0) //不断减去差的绝对值直到为0
        {
            a = b;
            b = temp;
            temp = abs(a - b);
        }
        return b;
    }
};