四平方和问题高效枚举算法及C++实现

根据题目描述，这是一个典型的四平方和问题，目标是找到字典序最小的四元组 (a, b, c, d) 使得 a² + b² + c² + d² = N，且 0 ≤ a ≤ b ≤ c ≤ d。 **解题思路：** - 因为要求字典序最小，所以优先固定 a，然后 b，再 c，最后算 d。 - N < 5×10⁶，所以 a 的最大值约为 √N ≈ 2236，可以承受 O(√N²) 的复杂度，但更高效的是用哈希表预先存储两数平方和。 - 为了字典序最小，可以预先计算所有可能的 c² + d²，并记录最小的 c 和 d 组合，然后在遍历 a 和 b 时查找。 **高效算法：** 1. 预计算一个数组 `res`，大小为 N+1，记录对于每个值 `sum = c² + d²` 的最小 `c`（或直接记录 c 和 d）。 2. 然后三重循环 a, b, c，直接计算 d = N - a² - b² - c²，检查 d 是否完全平方且 ≥ c。 3. 也可以直接四重循环，但会超时，所以用预计算优化。 这里给出一个 **O(N)** 预计算 + **O(√N³)** 枚举解法： ```cpp #include <iostream> #include <cmath> using namespace std; int main() { int n; cin >> n; int res[5000005] = {0}; // 记录最小值，初始为 -1 表示未记录 int maxn = sqrt(n) + 1; // 预计算所有可能的 c² + d²，记录最小的 c 值 for (int c = 0; c * c <= n; ++c) { for (int d = c; d * d + c * c <= n; ++d) { int s = c * c + d * d; if (res[s] == 0) { res[s] = c; // 记录最小的 c } } } // 枚举 a, b for (int a = 0; a * a <= n; ++a) { for (int b = a; a * a + b * b <= n; ++b) { int s1 = a * a + b * b; for (int c = b; c * c + s1 <= n; ++c) { int s2 = s1 + c * c; int d2 = n - s2; int d = sqrt(d2); if (d * d == d2 && d >= c) { cout << a << " " << b << " " << c << " " << d << endl; return 0; } } } } return 0; } ``` **更优化方案：** 利用预计算的 `res` 数组，避免最内层循环： ```cpp #include <iostream> #include <cmath> using namespace std; int main() { int n; cin >> n; int maxn = sqrt(n) + 1; // 预计算 c² + d² 对应的最小 c int res[5000001]; fill(res, res + n + 1, -1); for (int c = 0; c * c <= n; ++c) { for (int d = c; c * c + d * d <= n; ++d) { int s = c * c + d * d; if (res[s] == -1) { res[s] = c; } } } // 枚举 a, b for (int a = 0; a * a <= n; ++a) { for (int b = a; a * a + b * b <= n; ++b) { int s1 = a * a + b * b; for (int c = b; c * c + s1 <= n; ++c) { int s2 = s1 + c * c; int d2 = n - s2; if (res[d2] != -1 && res[d2] >= c) { int d = sqrt(d2); cout << a << " " << b << " " << c << " " << d << endl; return 0; } } } } return 0; } ``` **注意：** - 按照字典序，a、b、c、d 依次递增，所以枚举顺序就是从 a 最小开始，符合要求。 - 预计算数组大小要足够大（n+1），避免越界。 - 用 `fill` 初始化数组为 -1，表示未记录。 这种解法时间复杂度约为 O(√N³) ≈ (2236)³ ≈ 1.1×10¹⁰，仍然可能超时。但实际运行时，因为 a、b 较小，c 较大时 d² 会很接近 n，所以循环次数远小于理论上限，通常能通过。若需更高效，可进一步优化为 O(N) 枚举 a、b 并查表。 **替代方案（推荐）：** - 只用两层循环 a、b，然后查表得到 c、d： ```cpp #include <iostream> #include <cmath> using namespace std; int main() { int n; cin >> n; int maxn = sqrt(n) + 1; // 预计算 c² + d² 对应的最小 c 和 d int resC[5000001]; int resD[5000001]; for (int i = 0; i <= n; ++i) { resC[i] = -1; resD[i] = -1; } for (int c = 0; c * c <= n; ++c) { for (int d = c; c * c + d * d <= n; ++d) { int s = c * c + d * d; if (resC[s] == -1) { resC[s] = c; resD[s] = d; } } } // 枚举 a, b for (int a = 0; a * a <= n; ++a) { for (int b = a; a * a + b * b <= n; ++b) { int rem = n - (a * a + b * b); if (resC[rem] != -1 && resC[rem] >= b) { cout << a << " " << b << " " << resC[rem] << " " << resD[rem] << endl; return 0; } } } return 0; } ``` 这个版本时间复杂度为 O(√N²) ≈ 5×10⁶，非常快。 **开发建议：** - 注意数组大小，N 最大接近 500 万，int 数组足够。 - 用 `fill` 或循环初始化比 `memset` 更方便。 - 在遍历时注意整数溢出（c*c 可能接近 2.5×10⁷，int 可存，但 c*c + d*d 可能超过 10⁷，仍安全）。 ######[AI写代码神器 | 1630点数解答 | 2026-08-29 20:42:27]