网站建设交流发言材料,wordpress电影下载,重庆医院网站建设,建设网站的企业哪家好因为任何一个数都可以表示为若干个质数幂的乘积。
比如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
