欧几里德求最大公约数

欧几里德求最大公约数也是就辗转相除法，是最基础最简单的算法之一

求最大公约数

int gcd1(int a, int b){
    if (a < b){
        swap(a, b);
    }
    return b == 0 ? a : gcd1(b,a%b);
}
int gcd2(int a, int b){
    if (a < b){
        swap(a, b);
    }
    while (!(a%b)==0){
        int temp = a;
        a = b;
        b = temp%b;
    }
    return b;
}

求最小公倍数

int gds(int a, int b){
    return a*b / gcd2(a, b);
}