GESP 八级 · GESP 202506 C++ 八级 第 11 题

下面 count_triple 函数的时间复杂度为（ ）。

int gcd(int a, int b) {
    if (a == 0)
        return b;
    return gcd(b % a, a);
}
int count_triple(int n) {
    int cnt = 0;
    for (int v = 1; v * v * 4 <= n; v++)
        for (int u = v + 1; u * (u + v) * 2 <= n; u += 2)
            if (gcd(u, v) == 1) {
                int a = u * u - v * v;
                int b = u * v * 2;
                int c = u * u + v * v;
                cnt += n / (a + b + c);
            }
    return cnt;
}

辗转相除法求最大公约数：gcd(a,b) = gcd(b, a%b)，当b=0时返回a。时间复杂度O(log min(a,b))。

分析复杂度时注意外层循环和内层循环的关联。例如内外两层都到n的循环不一定是O(n²)，要看内层是否每次都在缩小。

【考点】循环复杂度分析｜欧几里得算法（GCD）时间复杂度

GESP 八级 C++ 考纲中“算法效率分析”模块的重点题型，专门考察对嵌套循环总迭代次数与内部函数复杂度叠加关系的直觉缺失。命题人卡住的是考生往往只盯着循环变量范围，却忘了 GCD 本身是 O(log n) 的。

先看外循环 v 到 sqrt(n)/2，内循环 u 从 v+1 步进 2 到约 sqrt(n)，故总迭代次数为 sqrt(n)×sqrt(n)=O(n)。再看循环体里的 gcd(u, v)，欧几里得算法最坏情况是 O(log min(u,v))，这里 u,v≤sqrt(n)，所以单次 GCD 是 O(log n)。整体时间复杂度 = 迭代次数 × 单次成本 = O(n log n)。

陷阱在于四个选项的“诱惑力”：A 项 O(n) 是只算了循环次数、完全忽略 GCD 的代价；B 项 O(n²) 是误把循环边界当成 n 级；D 项 O(n² log n) 则是把“双层循环”与“GCD”错误叠加。最阴险的细节是 u+=2 看似减少迭代，但 GCD 的 log n 因子仍是决定项——只背结论、不理解算法本质，就会掉进这个坑。

若把 gcd 换成常数时间判断，答案退化为 A；若外循环改到 v≤n，则变成 O(n^(1.5) log n)。刷到类似题先问：循环总次数是多少？内部操作复杂度是多少？两者相乘才是真相。