LCM — Least Common Multiple 最小公倍数

本文主要是介绍LCM — Least Common Multiple 最小公倍数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

因为任何一个数都可以表示为若干个质数幂的乘积。

比如75 = 3*5*5，即 2^0 * 3^1 * 5^2 * 7^0 ...

那么对于两个数来说，gcd就是他们取每个质数的较小幂的乘积，lcm则相反。显然，这些幂加起来就是他们乘积。

gcd(a,b) * lcm(a,b) = a*b

OI Wiki:

板子： 

int gcd(int a, int b)
{if (a < b)swap(a, b);if (b == 0)return a;return gcd(b, a % b);
}
int lcm(int a, int b)
{return a * b / gcd(a, b);
}

注意：

仅两个数时符合lcm = a*b/gcd。多个数就不成立了。

比如：

e.g.:4 5 8lcm: 40而 gcd(8,5,4) == 18*5*4 == 160

练习：Problem - C - Codeforces

这篇关于LCM — Least Common Multiple 最小公倍数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---