【C语言】【牛客刷题】【BC115】 小乐乐与欧几里得

   🥰   描述
        小乐乐最近在课上学习了如何求两个正整数的最大公约数与最小公倍数，但是他竟然不会求两个正整数的最大公约数与最小公倍数之和，请你帮助他解决这个问题。
        输入描述：每组输入包含两个正整数n和m。(1 ≤ n ≤ 109，1 ≤ m ≤ 109)
        输出描述：对于每组输入，输出一个正整数，为n和m的最大公约数与最小公倍数之和。
        示例1
        输入：10 20
        输出：30
        示例2
        输入：15 20
        输出：65

             

🤬代码展示（这是一种不考虑时间复杂度的算法）：

 
 
#define _CRT_SECURE_NO_WARNINGS
#include
 
int main()
{
	int n = 0;
	int m = 0;
	while (~scanf("%d %d", &n, &m))
	{
		int max = n > m ? n : m;
		int min = n > m ? m : n;
 
		int commonMax = max;	// 表是最大公约数。
		int commonMin = min;	// 表示最小公倍数。
 
		// 先求最大公约数
		while (1)
		{
			if (n % commonMax == 0 && m % commonMin == 0)
			{
				break;
			}
			commonMax--;
		}
		// 程序走到这里commonMax就是最大公约数。
		while (1)
		{
			if (commonMin % n  == 0 && commonMin % m == 0)
			{
				break;
			}
			commonMin++;
		}
		// 程序走到这里commonMin就是最小公约数。
		printf("%d\n",commonMax+commonMin);
 
	return 0;
}

        但是实际来说在牛客网上是跑步过的，因为这道题还涉及了时间复杂度的要求。

那么接下来我们来看一下另一种解决方法：

#include
 
int main()
{
	long n = 0;
	long m = 0;
	while (~scanf("%ld %ld", &n, &m))
	{
		long tempN = n;
		long tempM = m;
		long result = 0;
		// 利用辗转相除法求出最大公约数，
		while (result = tempN % tempM)
		{
			tempN = tempM;
			tempM = result;
		}
		// 程序走到这里tempN就是最大公约数
		// 然后我们在利用一个规律 n*m/最大公约数（tempM） = 最小公倍数。
		printf("%ld\n",n*m/tempM + tempM);
 
	}
    return 0 ;
}