为何我的LCM和HCF求解代码在部分测试用例中运行失败？

初始代码失败原因：整数溢出导致错误LCM计算 #

初始代码里计算LCM的逻辑是通过start = start*i不断放大最大值来找公倍数，这个逻辑有致命问题：

• 当输入数值较大时，start会快速超出long long的存储范围，触发整数溢出。比如测试用例113094和9449384，多次乘法后start溢出变为0，而0对任何整数取模结果都是0，刚好满足start%A==0&&start%B==0的条件，导致错误地把lcm赋值为0。
• 这种暴力乘法的方式效率极低，就算没溢出，也会因为循环次数过多超时。

修改后代码的潜在问题 #

修改后的代码改用start = start + org（每次累加最大值）的方式，虽然避免了快速溢出，但依然有两个硬伤：

1. 效率极差：对较大的数值对，需要循环极多次才能找到LCM，极端情况直接超时。比如本次测试用例，要累加(113094/2)次才能得到正确结果，循环次数超5万次，完全没必要。
2. 仍有溢出风险：如果LCM本身超过long long的最大值，累加过程中依然会溢出，导致错误结果。

正确解决方案：利用HCF与LCM的数学关系 #

数学上，两个数的LCM和HCF满足公式：LCM(A,B) = (A*B)/HCF(A,B)，用这个公式直接计算既高效又能规避溢出风险（注意先除以HCF再相乘，避免中间结果溢出）。

修正后的代码示例：

vector<long long> lcmAndGcd(long long A , long long B) {
    long long a = A, b = B;
    // 辗转相除法计算HCF
    while(a > 0 && b > 0) {
        if(a > b)
            a = a % b;
        else
            b = b % a;
    }
    long long hcf = (a == 0) ? b : a;
    // 先除后乘避免中间结果溢出
    long long lcm = (A / hcf) * B;
    return {lcm, hcf};
}

说明 #

• 先执行A/hcf再乘B，因为A一定能被hcf整除，这样能缩小中间结果的规模，最大程度避免整数溢出。
• 原代码里辗转相除法计算HCF的逻辑是正确的，无需修改。

内容的提问来源于stack exchange，提问作者Nikhil Kumar