最小公倍数(LCM)

定理

$$lcm(a,b)=\frac{a*b}{gcd(a,b)}$$

代码实现

int gcd(int a,int b)
{
	if(b==0) return a;
	return gcd(b,a%b);
}
int lcm(int a,int b)
{
	return a/gcd(a,b)*b;//先除后乘，防止爆炸
}