如何用C++实现O(log n)时间复杂度的HCF和LCM求解（含vector）

你的暴力枚举法通过从两数较小值向下遍历寻找最大公约数，时间复杂度为O(n)，无法满足O(log n)的要求。最优解决方案是使用欧几里得算法（辗转相除法），该算法通过不断取余缩小问题规模，时间复杂度为O(log(min(A,B)))，完全符合需求。

欧几里得算法核心原理 #

对于两个正整数A和B，最大公约数满足：
HCF(A, B) = HCF(B, A % B)
重复此过程直到余数为0，此时的除数就是两数的最大公约数。

优化后的完整代码 #

class Solution 
{
public:
    // 实现欧几里得算法计算HCF
    long long computeHCF(long long A, long long B) {
        while (B != 0) {
            long long temp = B;
            B = A % B;
            A = temp;
        }
        return A;
    }

    vector<long long> lcmAndGcd(long long A , long long B)
    {
        long long hcf = computeHCF(A, B);
        // 先除法再乘法，避免A*B直接相乘导致的long long溢出问题
        long long lcm = (A / hcf) * B;
        vector<long long> v;
        v.push_back(lcm);
        v.push_back(hcf);
        return v;
    }
};

关键改动说明 #

• 替换HCF计算逻辑：用欧几里得算法替代暴力枚举，将时间复杂度从O(n)降到O(log n)
• 避免溢出风险：LCM计算采用(A/hcf)*B而非(A*B)/hcf，因为当A、B为极大值时，直接相乘会超出long long的存储范围，先除以HCF（保证整除）再相乘可规避此问题
• 保持输出兼容：返回的vector仍按原代码顺序存储LCM和HCF，不影响原有调用逻辑

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