题解 | #小乐乐与欧几里得#

这道题目有下面几个难点： 1.存储的数字可能超出int上限 2.寻找最大公约数和最小公倍数可能会超时

解决方法： 1.对于超出上限，我们只需要使用long long类型就行。 2.对于超时问题，主要原因是数字太大，如果使用逐渐+1/-1进行判断，肯定会超时。所以要使用更快的算法，对于最大公约数，要使用欧几里得算法，最小公倍数要使用两数乘积=最大公约数和最小公倍数乘积的数学原理。对于欧几里得算法的原理，百度上有。

代码如下：

#define MAX(a,b) ((a > b)? (a) : (b))
#define MIN(a,b) ((a > b)? (b) : (a))

long long func1(long long a, long long b)
{
	if (a % b == 0)
		return b;
	else
		return func1(b, a % b);
}

int main()
{
	long long a = 0;
	long long b = 0;
	scanf("%lld %lld", &a, &b);
	long long result = func1(MAX(a, b), MIN(a, b));
	printf("%lld", result + a * b / result);
	return 0;
}