GESP 八级 · GESP 202509 C++ 八级 第 12 题

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

int gcd(int m, int n) {
    if (m == 0) return n;
    return gcd(n % m, m);
}
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 算法复杂度｜对数时间复杂度

1. 🎯 考纲定位

本题考查 GESP 八级「算法复杂度分析」模块核心能力。命题人卡住绝大多数考生的弱点在于：看到两层循环就下意识判定 $O(n^2)$，却忽略了循环边界的实际迭代次数和对数级 GCD 调用成本。这是八级考生从「语法实现」跨越到「复杂度量化」的关键分水岭。