题解 | #求最小公倍数#

解题思路

最小公倍数 最大公因子

1. $\mathrm{\mid }ab\mathrm{\mid }=gcd(a,b)lcm(a,b)|ab|\; =\; gcd(a,\; b)lcm(a,\; b)$ 其中，gcd是最大公因数， lcm是最小公倍数
2. $lcm=\mathrm{\mid }ab\mathrm{\mid }\mathrm{/}gcd(a,b)lcm\; =\; |ab|\; /\; gcd(a,b)$ 明确
3. 如何求 $gcd(a,b)gcd(a,\; b)$ —— 辗转相除法

代码

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

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