【数论】GCD与LCM

最大公约数gcd

板子

int gcd(int a, int b)
{
    return b > 0 ? gcd(b, a % b) : a;
}

最小公倍数lcm

板子

int lcm(int a, int b)
{
	return a / gcd(a, b) * b;
}

性质

1. gcd(a, b) * lcm(a, b) = a * b
2. gcd(a, b) = gcd(a, b - a)
3. gcd(a, b, c) = gcd(a, gcd(b, c))