最大公约数和最小公倍数

最大公约数

最大公约数是能够被给定两个数整除的最大的数。
设a,b,gcd,a>b,gcd是a和b的最大公约数。
则a = gcd * a’,b = gcd * b’,a % b = gcd × (a’ - b’)。
所以有gcd(a , b) = gcd(b , a % b)。

int gcd(const int& a, const int& b)
{
    return b ? gcd(b, a % b) : a;
}

最小公倍数

最小公倍数是能够将给定两个数整除的最小的数。
设a, b, gcd, lcm。
容易知道：最小公倍数 = a * b / gcd;

int lcm(const int& a, const int& b)
{
    return a / gcd(a, b) * b;//先除最大公约数防止溢出
}