四平方和定理问题的高效解法及Python实现指南

根据题目要求，我们需要找到所有满足条件的 (a, b, c, d) 组合，使得 a² + b² + c² + d² = N，且 0 ≤ a ≤ b ≤ c ≤ d。在所有满足条件的组合中，按字典序（即先比较 a，再 b，再 c，再 d）输出最小的一个。 **解题思路：** - 由于 **N < 5×10⁶**，如果直接四重循环枚举 a、b、c、d，时间复杂度会达到 O(N²) 甚至更高，不可行。 - 需要**优化枚举**： - 枚举 a 和 b，计算剩余的平方和 `s = N - a² - b²`。 - 然后枚举 c，使得 `d = sqrt(s - c²)` 为整数且 **c ≤ d**。 - 这样时间复杂为 O(N) 级别，且方便按字典序找到最小解。 - 因为题目要求输出字典序最小的组合，我们按 **a 从小到大、再 b 从小到大**的顺序枚举，一旦找到满足条件的组合，立即输出即可。 --- ### 💡 实现步骤 1. 读入正整数 N。 2. 循环 `a` 从 0 到 `sqrt(N/4)`（因为要满足 a ≤ b ≤ c ≤ d，且 a 最小）。 3. 循环 `b` 从 `a` 到 `sqrt((N - a²)/3)`。 4. 计算 `s = N - a² - b²`。 5. 循环 `c` 从 `b` 到 `sqrt(s/2)`。 6. 计算 `d² = s - c²`，令 `d = int(sqrt(d²))`，检查 `d*d == d²` 且 `c ≤ d`，若成立则输出。 --- ### 📝 代码实现（Python） ```python import math def main(): N = int(input().strip()) limit = int(math.isqrt(N)) # 枚举 a for a in range(limit + 1): a2 = a * a if a2 * 4 > N: break # 枚举 b，保证 a <= b for b in range(a, limit + 1): b2 = b * b s = N - a2 - b2 if s < 0 or b2 + b2 < s: # 提前剪枝：剩余部分必须至少为 b²且不大于 b²*2？ # 实际上这里需要根据 b 与 c、d 的关系调整，这里简单处理 # 因为 a <= b <= c <= d，所以 s 必须满足 0 <= s <= (b² + ... 复杂) continue # 枚举 c，保证 b <= c # 此处优化：c 从 b 到 sqrt(s/2)，因为 c <= d 且 c² + d² = s，所以 c² <= s/2 max_c = int(math.isqrt(s // 2)) for c in range(b, max_c + 1): c2 = c * c d2 = s - c2 d = int(math.isqrt(d2)) if d * d == d2 and c <= d: # 找到字典序最小的解，直接输出 print(a, b, c, d) return if __name__ == "__main__": main() ``` **但上面的代码剪枝不够严谨，可能导致剪枝过早，跳过了一些可能解。** 更稳妥的写法是： ```python import math def main(): N = int(input().strip()) # 先计算平方根表，避免重复开方 root = [int(math.isqrt(i)) for i in range(N + 1)] # 这样会占用内存，但N为5e6尚可 for a in range(int(math.isqrt(N)) + 1): a2 = a * a if a2 * 4 > N: break for b in range(a, int(math.isqrt(N - a2)) + 1): b2 = b * b s = N - a2 - b2 if s < 0: continue # 此时 c >= b，且 c <= d，所以 c 最大为 sqrt(s/2) max_c = int(math.sqrt(s // 2)) for c in range(b, max_c + 1): c2 = c * c d2 = s - c2 d = int(math.sqrt(d2)) if d * d == d2 and c <= d: print(a, b, c, d) return if __name__ == "__main__": main() ``` --- ### 🧠 复杂度分析 - 外层循环 a 大约到 √N（约 2236），b 也要到 √N，理论上 O(N)，但通过数学剪枝，实际运行较快。 - 空间复杂度 O(1)（如果不预计算平方根表）或 O(N)（若用表）。 --- ### ⚠️ 注意点 1. **边界条件**：确保枚举范围正确，尤其是 `a` 的最大值必须满足 `4*a² ≤ N`，因为 a 是最小数。 2. **字典序**：从最小的 a 开始，内部从最小的 b 开始，一旦找到解即为最小字典序，直接返回。 3. **整数平方判断**：使用 `int(math.isqrt(x))` 然后判断平方是否等于 x，避免浮点误差。 4. **剪枝**：如果 `s < 0` 直接跳过；若 `b² > s/2` 则 c 无法满足条件，也可跳过。 --- ### 🚀 开发建议 - 可以**预计算平方表**，将平方值存入列表，查询时直接使用，减少重复计算。 - 对于更大的 N（如 10^7 以上），建议使用**哈希集合存储平方数**，以 O(1) 判断 d² 是否为平方数。 - 若要求更快，可以使用**双指针**优化 c 和 d 的搜索，但本题数据规模小，不需要。 --- ### 📚 参考测试 输入： ``` 5 ``` 输出： ``` 0 0 1 2 ``` 输入： ``` 7 ``` 输出： ``` 0 1 1 2 ``` --- ######[AI写代码神器 | 1431点数解答 | 2026-08-16 09:42:04]