[数据结构与算法]《C语言入门》最小公倍数与最大公约数之和问题求解

目录

? ? ? ? ? ? ?1.问题描述

? ? ? ? ? ? ?2.算法求解及代码

1.问题描述

描述

小乐乐最近在课上学习了如何求两个正整数的最大公约数与最小公倍数，但是他竟然不会求两个正整数的最大公约数与最小公倍数之和，请你帮助他解决这个问题。

输入描述：

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

输出描述：

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

题目代码链接小乐乐与欧几里得_牛客题霸_牛客网 (nowcoder.com)

2.算法求解及代码

我们初学这看到这个题目首先想到的肯定时暴力求解，类似与以下代码：

#include<stdio.h>

int main()
{
    int n = 0;
    int m = 0;
    scanf("%d %d", &n, &m);
    int a = n > m ? n : m;
    int b = a;
    int i = 0;
    while (1)
    {
        if (b % m == 0 && b % n == 0)
            break;
        b++;
    }
    for (i = a; i > 1; i--)
    {
        if (m % i == 0 && n % i == 0)
            break;
    }
    printf("%d", i + b);
    return 0;
}

于是我们就得到了这个结果

?为了超时问题，减少计算次数，增加效率，我们这里使用一下两种算法。

辗转相除法（欧几里得法）：我们使用需要求最大公约数的两个数字进行求余，如a%b，若a%b==0，则b就是这两个数字的最大公约数，若a%b!=0，我们将b的值赋给a，将求余的结果赋值给b,再进行以上操作，直到a%b==0为止，我们将上述算法套入循环中实现。

?关于求最小公倍数的方法我们这里可以利用这样一个等式，两个数的乘积=这两个数的最小公倍数*这两个数的最大公约数。我们这里使用这样的方法求最小公倍数。

?因本题中可能会出现两个整型相乘，为了更好的存储这些数字，我们使用long long来对本题的数据进行定义。完整代码如下：

int main()
{
    long long n = 0;
    long long m = 0;
    scanf("%ld %ld", &n, &m);
    long long a = 0;
    long long x = m;
    long long y = n;
    while (1)
    {
        a = n % m;
        if (a == 0)
            break;
        n = m;
        m = a;
    }
    long long  b = (x * y) / m;
    printf("%ld", m + b);
    return 0;
}

本文到此结束，欢迎大家点赞评论互关，感谢大家的阅读，祝大家万事如意。