12987.平方之和

markdown
复制
1# 平方之和 题解
2
3## 题目分析
4
5本题要求对于给定的 $n$ 个正整数 $a_i$，分别判断它是否能写成两个**正整数**的平方和，即是否存在 $x, y \in \mathbb{Z}^+$，使得
6
7\[
8x^2 + y^2 = a_i
9\]
10
11如果存在，输出 `Yes`，否则输出 `No`。
12
13数据范围较小：$n \le 10$，$a_i \le 10^6$，因此使用较为直接的方法即可通过。
14
15## 解题思路
16
17我们不妨枚举其中一个数 $x$ 的取值，然后检查 $a_i - x^2$ 是否是一个完全平方数。由于 $x, y$ 均为正整数，因此 $x$ 至少为 $1$，且 $x^2 < a_i$（否则 $y^2 \le 0$，$y$ 将不可能是正整数）。
18
19具体做法：
201. 令 $x$ 从 $1$ 开始，依次枚举，直到 $x^2 \ge a_i$ 时停止。
212. 对于每个 $x$，计算 $j = a_i - x^2$。
223. 判断 $j$ 是否为完全平方数（即是否存在正整数 $y$ 使得 $y^2 = j$）。
234. 若找到一组满足条件的 $x, y$，直接输出 `Yes`；若所有 $x$ 都枚举完后仍未找到，输出 `No`。
24
25## 算法说明
26
27### 判断完全平方数
28可以用 `sqrt` 函数计算 $j$ 的平方根，然后检查平方根的整数部分的平方是否等于 $j$ 本身。由于浮点数可能存在精度问题，一种更安全的写法是：
29
30```cpp
31int y = (int)sqrt(j);
32while ((y+1)*(y+1) <= j) y++;
33while (y*y > j) y--;
34return y*y == j;

不过在本题数据范围内，直接使用参考代码中的写法也能正常工作。

参考代码解释

cpp
复制
1#include<bits/stdc++.h>
2using namespace std;
3
4bool check(int x) {
5    int y = sqrt(x);
6    return y * y == x;
7}
8
9int main() {
10    int t;
11    cin >> t;
12    while (t--) {
13        int n;
14        cin >> n;
15        int fl = 0;
16        // 枚举 x，由于 x 为正整数且 x^2 < n
17        for (int i = 1; i * i < n; i++) {
18            int j = n - i * i;
19            if (check(j)) fl = 1;   // 若 j 是完全平方数，说明存在 y = sqrt(j)
20        }
21        if (fl) cout << "Yes\n";
22        else cout << "No\n";
23    }
24    return 0;
25}

代码解析：

• check(x) 函数用 sqrt 获得整数平方根，再验证平方是否等于原数。
• 主循环读入测试次数 t，即 $n$。
• 对每个数 n（即 $a_i$），设置标志 fl = 0。
• 循环 for(int i = 1; i * i < n; i++) 枚举 $x$。条件 i * i < n 保证 $y^2 = n - i^2 > 0$，从而 $y$ 为正整数。
• 计算 j = n - i * i，若 check(j) 为真，则找到合法的 $y$，将 fl 置为 1。
• 最后根据 fl 输出答案。

时间复杂度分析

对于每个 $a_i$，我们枚举 $x$ 的范围大约是 $\sqrt{a_i}$ 级别，因此单次判断的时间复杂度为 $O(\sqrt{a_i})$。由于 $a_i \le 10^6$，$\sqrt{a_i} \le 1000$，且 $n \le 10$，所以总计算量非常小，可以在极小的时间内运行完毕。

总时间复杂度：$O(n \sqrt{\max a_i})$，空间复杂度 $O(1)$。

总结

本题是一道基础的枚举与平方数判断问题，核心在于将两数平方和转化为“固定一个数，验证另一个数是否为完全平方数”的思路，并通过简单的循环完成判断。对于初学者来说，是练习循环和函数设计的好题目。