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

当我第一次看到这道题的时候，感觉并不是特别难，首先映入脑海的便是暴力解法：
// #include <stdio.h>
// int main()
// {
//     int n = 0, m = 0;
//     int maxDiv = 0, minMul = 0;
//     scanf("%d %d", &n, &m);
//     //最大公约数
//     int max = n > m ? n : m;
//     int min = n < m ? n : m;
//     int i = 0;
//     for(i = min; i >= 0; i --)
//     {
//         if(max % i == 0 && min % i == 0)
//         {
//             maxDiv = i;
//             break;
//         }
//     }
//     int tmp = max;
//     while(1){
//         if(tmp % max == 0 && tmp % min == 0){
//             minMul = tmp;
//             break;
//         }
//         tmp ++;
//     }
//     printf("%d", maxDiv + minMul);
//     return 0;
// }

``` js
之后我有自信满满地点了测试示例，成功解了出来，可是提交了之后才发现算法过于复杂了，然后
便转向评论区地da lao讨教，又去度娘哪里找到了欧几里得公式，不得不佩服这位数学家地思维逻辑，
并且发现之前的int类型是不够用的，特意换上了long类型，终于过去了哈~：
#include <stdio.h>
//欧几里得算法思想示例：
// 1997 / 615 = 3 (余 152)
// 615 / 152 = 4(余7)
// 152 / 7 = 21(余5)
// 7 / 5 = 1 (余2)
// 5 / 2 = 2 (余1)
// 2 / 1 = 2 (余0)
// 至此，最大公约数为1
//最小公倍数等于两数之积除以其最大公约数
int main()
{
    long n = 0, m = 0;
    scanf("%d %d", &n, &m);
    long maxNum = n > m ? n : m;
    long minNum = n < m ? n : m;
    long remainder = -1;
    long maxDiv = -1;
    while(1)
    {
        remainder = maxNum % minNum;
        if(remainder == 0)
        {
            maxDiv = minNum;
            break;
        }
        maxNum = minNum;
        minNum = remainder;
    }
    long minMul = n * m / maxDiv;
    printf("%ld",maxDiv + minMul);
    return 0;
}

``` js