题干信息解读

题目要求计算对于每个整数 i（从 1 到 n），满足条件 1≤x,y,z 且 x² + y² + z² + xy + yz + xz = i 的三元组 (x,y,z) 的数量 f(i)。最终输出 f(1) 到 f(n) 的所有值。

整体做题思路

我们可以通过枚举所有可能的三元组 (x,y,z)，计算它们对应的表达式值
s = x² + y² + z² + xy + yz + xz，并统计每个 s 出现的次数。由于 n 的最大值为 $10^4$ ，我们可以通过合理的枚举范围来确保算法的效率。
枚举时，我们可以假设 x≤y≤z 以减少重复计算，然后根据 x,y,z 的相等情况来确定对应的排列数：
①当 x=y=z 时，只有 1 种排列。
②当 x=y<z 或 x<y=z 时，有 3 种排列。
③当 x<y<z 时，有 6 种排列。

难点和注意事项

枚举范围的确定：需要确保枚举的 x,y,z 能够覆盖所有可能的 s≤n 的情况。
排列数的计算：根据 x,y,z 的相等情况正确计算对应的排列数。
时间复杂度的优化：通过合理的枚举顺序和范围，避免不必要的计算。

AC代码（如有雷同，纯属巧合）

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> f(n + 1, 0); // 初始化结果数组，f[0]到f[n]

    // 枚举所有可能的x, y, z组合
    for (int x = 1; x * x <= n; ++x) {
        for (int y = x; ; ++y) {
            // 计算x和y的部分表达式
            int part = x * x + y * y + x * y;
            if (part > n) break; // 如果部分表达式已经超过n，退出y的循环

            for (int z = y; ; ++z) {
                // 计算完整表达式
                int s = part + z * z + y * z + x * z;
                if (s > n) break; // 如果完整表达式超过n，退出z的循环

                int cnt;
                if (x == y && y == z) {
                    cnt = 1; // 三个数都相等，只有一种排列
                } else if (x == y || y == z) {
                    cnt = 3; // 有两个数相等，有三种排列
                } else {
                    cnt = 6; // 三个数都不相等，有六种排列
                }

                // 更新结果数组
                f[s] += cnt;
            }
        }
    }

    // 输出结果
    for (int i = 1; i <= n; ++i) {
        cout << f[i] << endl;
    }

    return 0;
}

复杂度分析

时间复杂度：枚举 x,y,z 的三重循环的时间复杂度约为 O($n^(3/2)$ )，因为每个循环的上限约为 $\sqrt{n}$。
空间复杂度：主要使用了一个长度为 n+1 的数组来存储结果，因此空间复杂度为 O(n)。

该算法在 n ≤ $10^4$ 的情况下能够高效运行，确保在合理时间内得到结果。