题目来源：牛客网编程入门训练--BC115  小乐乐与欧几里得

输入描述：

每组输入包含两个正整数n和m。(1 ≤ n ≤ 109，1 ≤ m ≤ 109)

输出描述：

对于每组输入，输出一个正整数，为n和m的最大公约数与最小公倍数之和。

解题思路：此题有多种解题方法，列如分别求出两数的最大公约数与最小公倍数，再将其相加。（大致方法：取两数较小数为初识化的最大公约数，依次--，直到找到能同时将其整除的数字再停下，即为最大公约数；最小公倍数类似，取两数较大数为初始化的最小公倍数，依次++，直到找到一个能同时将两数除尽的数字，即为最小公倍数）。

这种算法思想由于运算量比较大，某些网站限制通过时间，所以这里我们用效率更优的辗转相除法求出最大公约数，再将两数的乘积除以最大公约数即为最小公倍数。 

下面上代码，需要注意的点在代码中以注释形式给出：

#include <stdio.h>
int main()
{
	long long m = 0; // 数字万一较大，用长长整型接收
	long long n = 0;
	scanf("%d %d", &m, &n);
	long long m1 = m;
	long long n1 = n; // 防止辗转相除过程中原数字改变，影响最小公倍数结果
	long long c = 0;
	while (c=m1%n1) //除尽的话n1即为最大公约数
	{
		m1 = n1;
		n1 = c;  
	}
	long long max = (m*n) / n1;// max为最小公倍数
	printf("%lld\n", max + n1);
	
	return 0;

}

 

 

over ~