C++代码运行时长优化：解决大输入场景下运行超2秒问题

原代码性能瓶颈 #

• 无效遍历占比极高：原代码双层循环的边界设为1~num，但只要y或z大于√num，y*y/z*z就已经大于num，后续累加的平方项均为正整数，ans必然大于num，99%以上的循环迭代完全没有计算意义。
• 时间复杂度过高：单组用例复杂度为O(num²)，num规模到1e3就会产生百万次迭代，到1e4就会产生亿次迭代，大规模输入下必然超时。
• 重复计算冗余：循环内多次调用gcd(y,z)，重复计算gcd值、gcd平方、lcm平方，累计开销极高。
• IO效率低：默认开启的C++/C标准IO同步会让cin/cout速度比原生C IO慢3~10倍，再加上endl每次强制刷新缓冲区，大规模输入输出时额外耗时明显。
• 未做数学化简：核心计算式可以通过数论公式因式分解，从根源上减少计算量。
• 命名存在潜在冲突：原代码用标准库同名标识符pair作为变量名，开启using namespace std时可能引发未知问题。

核心数学推导（最高优先级优化） #

设g = gcd(y,z)，令y = g*a，z = g*b，此时gcd(a,b) = 1，根据lcm和gcd的关系lcm(y,z) = g*a*b，代入ans的计算式做因式分解：

ans = (g*a)² + (g*b)² + g² + (g*a*b)²
    = g² * (a² + b² + 1 + a²b²)
    = g² * (a²+1)*(b²+1)

推导后可以直接得到结论：num必须能被g²整除，且num/g²可以拆成两个互质整数a、b对应(a²+1)、(b²+1)的乘积，不需要遍历所有y、z组合，只需要枚举num的因数即可完成计算。

可落地优化步骤 #

1. 优先优化IO效率，在main函数开头加三行代码关闭同步，输出换行直接用'\n'代替endl，即可把cin/cout速度提升到和scanf/printf同一水平：

   ios::sync_with_stdio(false);
   cin.tie(nullptr);
   cout.tie(nullptr);
   

2. 修正循环边界：就算不做数学重构，也可以直接把y、z的循环上界从num改成(long long)sqrt(num)，直接砍掉99%以上的无效迭代。同时循环内只计算一次gcd，存为临时变量，lcm用y/g*z计算（避免y*z溢出，且不需要重复调用gcd），所有平方项计算一次后复用，不要重复运算。
3. 基于数学公式重构计算逻辑：枚举所有满足g²整除num的g值，再对num/g²枚举因数对（u,v），判断u-1、v-1是不是完全平方数，开平方得到a、b后验证gcd(a,b)是否为1，统计符合条件的(y=ga, z=gb)对即可，单组用例复杂度直接降到O(d(num))级别，d(num)是num的因数个数，通常不超过1000，哪怕num到1e6也能微秒级返回结果。
4. 离线打表预处理：如果题目提前给出num的最大值上限（比如常见编程题上限1e5、1e6），可以在程序启动时先预处理所有可能num对应的答案存在数组里，后续处理测试用例直接O(1)查表输出，哪怕有十万组测试用例也不会超时。
5. 修正变量命名：把原代码里的计数变量pair改名为cnt，避免和标准库类名冲突。

基础优化版参考代码（仅改边界、IO、重复计算，不重构逻辑） #

#include <iostream>
#include <numeric>
#include <cmath>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    long long test_cases, num, ans, x, cnt, y, z;
    cin >> test_cases;
    for(x=1; x<=test_cases; x++){
        cnt = 0;
        cin >> num;
        long long upper = sqrt(num);
        for(y=1; y<=upper; y++){
            long long y_sq = y*y;
            for(z=1; z<=upper; z++){
                long long z_sq = z*z;
                long long g = gcd(y,z);
                long long g_sq = g*g;
                long long l = y/g*z;
                long long l_sq = l*l;
                ans = y_sq + z_sq + g_sq + l_sq;
                if (ans == num) cnt++;
            }
        }
        cout << cnt << '\n';
    }
    return 0;
}

这个基础版本已经能把运行速度提升100倍以上，如果要处理更大规模的输入，直接套用前面的数学推导重构计算逻辑即可，速度还能再提升几个数量级。

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