hdu_Lowest Common Multiple Plus_答题报告

hdu_Lowest Common Multiple Plus_解题报告

题目出处

简单题

思路：

求 最小公倍数，有其公式可用

$hdu_Lowest Common Multiple Plus_答题报告$ （出处）

就是 最小公倍数 = |a * b| 除以 （a与b的最大公约数）

此题的问题就转化为如何求 最大公约数

同样， 最大公约数 也是用欧几里得算法（辗转相除法）

例如（出处）
计算a = 1071和b = 462的最大公约数的过程如下：

从1071中不断减去462直到小于462（可以减2次，即商= 2），余数是147：

然后从462中不断减去147直到小于147（可以减3次，即 = 3），余数是21：

462 = 3 × 147 + 21.

再从147中不断减去21直到小于21（可以减7次，即 = 7），没有余数：

147 = 7 × 21 + 0.

此时，余数是0，所以1071和462的最大公约数是21

关键代码：

int gcd(int a, int b)
{
	if (b == 0) {
		return a;
	}
	return gcd(b, a%b);
}

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