C++实现四平方和定理最小字典序解算法

我来帮你解决这个问题。这是一个典型的四平方和定理问题，需要找到字典序最小的表示方法。 ## 🎯 问题分析 我们需要找到满足 `a² + b² + c² + d² = N` 的一组解，其中 `0 ≤ a ≤ b ≤ c ≤ d`，并且这组解在字典序上最小。 ### 💡 解题思路 最简单的暴力枚举方法复杂度为 O(N²)，对于 N < 5×10⁶ 来说太慢。我们可以优化枚举策略： 1. **先枚举 a 和 b**，计算 `s = a² + b²` 2. **再枚举 c 和 d**，使得 `c² + d² = N - s` 通过合理的枚举顺序，我们可以保证第一个找到的解就是字典序最小的解。 ## 📝 C++ 代码实现 ```cpp #include <iostream> #include <cmath> using namespace std; int main() { int N; cin >> N; // 枚举 a for (int a = 0; a * a <= N; a++) { // 枚举 b，保证 a <= b for (int b = a; a * a + b * b <= N; b++) { // 枚举 c，保证 b <= c for (int c = b; a * a + b * b + c * c <= N; c++) { int sum = a * a + b * b + c * c; int d2 = N - sum; // 检查 d² 是否是完全平方数 int d = sqrt(d2); if (d * d == d2 && d >= c) { // 找到字典序最小的解 cout << a << " " << b << " " << c << " " << d << endl; return 0; } } } } return 0; } ``` ## 🔧 优化版本（更高效） ```cpp #include <iostream> #include <cmath> #include <vector> using namespace std; int main() { int N; cin >> N; // 预计算所有可能的 c² + d² 组合及其对应位置 // 使用哈希表存储 (value, c) 的映射关系 vector<vector<pair<int, int>>> hashTable(N + 1); // 预计算所有 c² + d² 的映射 for (int c = 0; c * c <= N; c++) { for (int d = c; c * c + d * d <= N; d++) { int value = c * c + d * d; hashTable[value].push_back({c, d}); } } // 枚举 a 和 b for (int a = 0; a * a <= N; a++) { for (int b = a; a * a + b * b <= N; b++) { int remaining = N - a * a - b * b; // 在哈希表中查找剩余部分 for (auto& pair : hashTable[remaining]) { int c = pair.first; int d = pair.second; // 确保 a <= b <= c <= d if (c >= b) { cout << a << " " << b << " " << c << " " << d << endl; return 0; } } } } return 0; } ``` ## 💡 算法复杂度分析 **暴力版本：** - 时间复杂度：O(N^(3/2))，最坏情况下需要枚举很多组合 - 空间复杂度：O(1) **优化版本：** - 预计算阶段：O(N) 时间，O(N) 空间 - 查找阶段：O(N^(3/4))，但实际运行更快 - 总空间复杂度：O(N) ## ⚠️ 注意事项 1. **枚举顺序很重要**：必须严格按照 a → b → c 的顺序枚举，才能保证找到的第一个解就是字典序最小的 2. **边界条件处理**： - 注意 `a * a <= N` 的条件限制 - 确保 `d * d == d2` 检查完全平方数 3. **性能优化建议**： - 使用 `int` 类型时注意溢出：a² 最大值约为 (2.2×10³)² = 5×10⁶，不会溢出 - 可以添加 `#pragma GCC optimize` 提升运行效率 ## 🔍 测试示例 **输入：** ``` 5 ``` **输出：** ``` 0 0 1 2 ``` **输入：** ``` 7 ``` **输出：** ``` 1 1 1 2 ``` **输入：** ``` 12 ``` **输出：** ``` 0 0 2 2 ``` ## 📚 扩展建议 - 如果 N 更大，可以考虑使用**Meet-in-the-Middle** 算法 - 可以使用**四平方和定理**的数学性质进一步优化 - 对于极端性能要求，可以预计算所有平方数并存储 ######[AI写代码神器 | 1134点数解答 | 2026-08-16 15:48:34]