返回题解分享
讨论 / 题解分享/ 帖子详情

最小公倍数 - 题解

/*
 思路
    思路一:
        1.由前面的欧几里得定理
        2. 最大公约数 gcd(a,b) = gcd(b,a%b)
        3. 最小公倍数 lcm(a,b) = (a*b)/gcd(a,b)
*/

#include <bits/stdc++.h>
using namespace std;

long gcd(long a, long b) {
    if (b == 0) return a;
    else return gcd(b,a%b);
}

long lcm(long a, long b) {
    return a/gcd(a,b)*b;
    //在计算乘积之前先除以 GCD。避免a*b (long * long)超出范围
}

int main()
{
    long a,b;
    cin >> a >> b;
    if ( a >= b ) cout << lcm(a,b) << endl;
    else cout << lcm(b,a) << endl;
    return 0;
}
0 回复 0 转发 0 喜欢 6 阅读
回复 (0)
默认 最新
暂无回复,快来抢沙发!