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

#include <stdio.h>
//先得知道最小公倍数等于两数之积除以其最大公约数
//所以只要先求最大公约数就行
//辗转相除法求最大公约数
int main() {
    long long n, m,z,q;//(1 ≤ n ≤ 109，1 ≤ m ≤ 109)
    scanf("%lld %lld",&n,&m);//使用long long类型，不然后面输出出现负数
    q=m*n;//先计算出两数之积
    while(1)
    {
        if(m>n)//判断m，n大小，使n%m！=0
        {
            z=n;
            n=m;
            m=z;   
        }
        if(n%m==0)//成立即m为最大公约数
        {
            break;
        }
        else 
        {
            z=m;
            m=n%m;
            n=z;//辗转相除法
        }
    }
    printf("%lld",m+q/m);//最小公倍数=q/m

    return 0;
}