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

#include <stdio.h>
//更相减损法
int main() {
    long long n = 0, m = 0, i = 1, max = 0,
              min = 0;  //使用long long类型变量，不然数据会溢出
    scanf("%lld%lld", &n, &m);

    //定义两个变量存储m,n并对大小进行判断
    max = m >= n ? m : n;
    min = m < n ? m : n;


    //两数均为偶数时，对数据进行预处理，减少计算量
    while (max % 2 == 0 && min % 2 == 0) {
        max /= 2;
        min /= 2;
        i *= 2;
    }

    while (max !=
            min) { //减数等于差时循环结束，减数即为最大公约数
        if (max > min)
            max -= min;  //把差赋值给max，返回循环判断
        else
            min -= max;  //把差赋值给min，返回循环判断
    }

    long long num1 = i * max;  //定义变量num1 用来存放最大公约数
    long long num2 = m * n / num1;  //定义变量num2 用来存放最小公倍数

    printf("%lld", num1 + num2);

    return 0;
}