求多项式方程w+2x²+3y³+4z⁴=n整数解数的高效算法问询

问题背景 #

需要计算满足方程 w + 2*x² + 3*y³ + 4*z⁴ = n 的非负整数解数量，要求禁止使用数组和内置函数，测试用例数量0<t<1000，n的取值范围0≤n≤10^6，时间限制5.5秒。当前的四层嵌套暴力循环解法效率太低，急需优化。

暴力解法的核心问题 #

你的代码里最外层遍历w的操作完全是冗余的：当x、y、z的取值确定后，2x² + 3y³ + 4z⁴的和是固定的，此时w必须等于 n - (2x² + 3y³ + 4z⁴)，只要这个结果是非负整数，就对应一个有效解。完全不需要逐个遍历w来验证。

优化思路 #

直接砍掉最外层的w循环，只遍历x、y、z三个变量：

• 遍历所有可能的x值，直到2*x*x > n停止；
• 对每个x，遍历所有可能的y值，直到2*x*x + 3*y*y*y > n停止；
• 对每个x、y，遍历所有可能的z值，直到2*x*x + 3*y*y*y +4*z*z*z*z >n停止；
• 只要上述三者的和s ≤n，就说明存在一个合法的w（w = n - s），此时计数器加1。

这样一来，循环层数从四层降到三层，计算量直接减少了一个数量级以上，完全能在时间限制内跑完所有测试用例。

优化后的代码 #

#include <iostream>

int main()
{
    int counter, t, n;
    std::cin >> t;

    for (int k = 0; k < t; k++)
    {
        std::cin >> n;
        counter = 0;

        // 遍历x的可能取值
        for (int x = 0;; x++)
        {
            int term_x = 2 * x * x;
            if (term_x > n) break;
            // 遍历y的可能取值
            for (int y = 0;; y++)
            {
                int term_y = 3 * y * y * y;
                int sum_xy = term_x + term_y;
                if (sum_xy > n) break;
                // 遍历z的可能取值
                for (int z = 0;; z++)
                {
                    int term_z = 4 * z * z * z * z;
                    int total = sum_xy + term_z;
                    if (total > n) break;
                    // 只要total <=n，w = n - total 就是合法解，计数器加1
                    counter++;
                }
            }
        }
        std::cout << counter << std::endl;
    }
    return 0;
}

效率对比 #

• 原暴力解法：一次n=1e6的测试，需要遍历1e6次w，配合x≈707次、y≈69次、z≈17次，总操作数约为 1e6 * 707 * 69 *17 ≈8e11，完全超出时间限制；
• 优化后解法：一次n=1e6的测试，总操作数约为 707 *69 *17 ≈8.3e4，即使t=1000，总操作数也只有8.3e7，远低于5.5秒能处理的操作量（通常CPU每秒能处理1e8~1e9次简单操作）。

额外注意 #

代码里没有使用任何数组或内置函数（比如sqrt），完全符合题目要求。每个循环的终止条件都是通过计算当前项的和是否超过n来判断，避免了使用内置数学函数。

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