四平方和定理C++高效解法及字典序最小输出策略

这个问题是典型的**四平方和定理**应用，需要找出满足 `a² + b² + c² + d² = N` 且 `0 ≤ a ≤ b ≤ c ≤ d` 的**字典序最小**的解。 ## 🧠 解题思路 **核心思想**：为了得到字典序最小的解，我们**从小到大**枚举 `a`、`b`、`c`，然后根据剩余值判断是否能找到合法的 `d`。 ### 📐 数学推导 - 由于 `0 ≤ a ≤ b ≤ c ≤ d`，且要求字典序最小，所以 `a`、`b`、`c` 都应尽量小。 - 当枚举到 `a`、`b`、`c` 后，剩余值为 `rem = N - a² - b² - c²`。 - 需要验证 `rem` 是否为完全平方数，且满足 `d ≥ c`。 - 由于 `N < 5×10⁶`，`d` 的最大值约为 `√(5×10⁶) ≈ 2236`，因此三重循环的复杂度在可接受范围内。 ### ⏱️ 复杂度分析 - 最坏情况下，`a`、`b`、`c` 都从 `0` 到 `√N` 枚举，三重循环约为 `(√N)³ = N^1.5`，对于 `N = 5×10⁶` 约为 `10^10`，**可能超时**。 - **优化**：提前用哈希表（或布尔数组）存储所有可能的 `c² + d²` 值及其对应的 `c`，将问题转化为两数之和。 ## 💻 C++ 代码实现（优化版） ```cpp #include <iostream> #include <cmath> using namespace std; int main() { int N; cin >> N; // 哈希表：记录 sum = c² + d² 的最小 c 值（保证字典序最小） // 由于 N < 5×10⁶，sum 最大为 N，数组大小足够 int hashTable[5000001] = {0}; // 初始化为0，但需要区分“未记录”和“c=0”的情况 // 使用 -1 表示未记录 for (int i = 0; i <= 5000000; i++) hashTable[i] = -1; // 预计算所有 c² + d² 的组合，存储最小的 c for (int c = 0; c * c <= N; c++) { for (int d = c; c * c + d * d <= N; d++) { int sum = c * c + d * d; if (hashTable[sum] == -1) { hashTable[sum] = c; // 只记录第一次（c最小）的情况 } } } // 枚举 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; // 查表找是否存在 c² + d² = rem if (hashTable[rem] != -1) { int c = hashTable[rem]; // 验证 d 是否为整数且 >= c int d = sqrt(rem - c * c); if (c * c + d * d == rem && c <= d) { // 需要确保字典序：a ≤ b ≤ c ≤ d if (b <= c) { cout << a << " " << b << " " << c << " " << d << endl; return 0; } } } } } return 0; } ``` ## 📝 代码关键点解析 | 部分 | 说明 | |------|------| | **预计算哈希表** | 遍历所有 `c ≤ d` 的组合，记录 `c² + d²` 对应的最小 `c` 值 | | **数组大小** | `N < 5×10⁶`，所以数组开到 `5000001` 即可覆盖所有可能和 | | **字典序保证** | 由于 `a`、`b` 从小到大枚举，且哈希表记录的是最小的 `c`，自然得到字典序最小解 | | **边界检查** | 使用 `c * c + d * d <= N` 提前终止内层循环，避免无用计算 | ## 🚀 算法优化说明 **为什么哈希表能大幅提速？** - 原始三重循环时间复杂度为 `O(N^1.5)`，对于 `5×10⁶` 会超时。 - 优化后：预计算 `O(N)`，枚举 `a`、`b` 为 `O(N)`，总复杂度 **O(N)**。 - 同时保证哈希表中记录的是**最小的 `c`**，从而确保最终结果是字典序最小的。 ## ⚠️ 注意事项 1. **整数溢出**：`c * c` 当 `c` 较大时可能超过 `int` 范围，建议使用 `long long` 或提前判断 `c <= sqrt(N)`。 2. **边界条件**：`N = 0` 时输出 `0 0 0 0`，本题输入为正整数所以不需特殊处理。 3. **哈希表初始化**：不能使用 `0` 作为“未记录”标记，因为合法的 `c` 可能为 `0`，需用 `-1` 或单独布尔数组。 ######[AI写代码神器 | 1264点数解答 | 2026-08-16 09:43:00]