网站建设费用差异大,本地服务器网站建设,工程公司注册经营范围,做网站公众号因为任何一个数都可以表示为若干个质数幂的乘积。
比如75 3*5*5#xff0c;即 2^0 * 3^1 * 5^2 * 7^0 ... 那么对于两个数来说#xff0c;gcd就是他们取每个质数的较小幂的乘积#xff0c;lcm则相反。显然#xff0c;这些幂加起来就是他们乘积。
gcd(a,b) * lcm(a,b) a…因为任何一个数都可以表示为若干个质数幂的乘积。
比如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
