题解 | 求最小公倍数

求最小公倍数

https://www.nowcoder.com/practice/22948c2cad484e0291350abad86136c3

#include <iostream>
using namespace std;

int main() 
{
    int a, b;
    cin >> a >> b;

    int n = a, m = b;
    while(m != 0)
    {
        int tmp = m;
        m = n % m;
        n = tmp;
    }

    cout << a*b/n << endl;
    return 0;
}

// 求两个数最小公倍数(LCM)的最快数学方法,核心是利用 最大公约数(GCD),公式为:
// LCM(a, b) = |a * b| / GCD(a, b)
// 原理:两个数的乘积等于它们的最大公约数和最小公倍数的乘积,即 a * b = GCD(a, b) * LCM(a, b),变形后得到最小公倍数公式。
// 优势:通过高效的 GCD 算法(如欧几里得算法),可快速计算 LCM,时间复杂度接近 O(log(min(a, b))),非常高效。

全部评论

相关推荐

码农索隆:想看offer细节
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务