题解

题目解析

• 输入输出：第一行输入整数 $n$，接下来 $n$ 行每行一个正整数 $a_i$；对每个 $a_i$ 判断是否能表示为两个正整数的平方和，能则输出 Yes，否则输出 No。
• 数据范围：根据 GESP 二级难度，通常 $n \leq 100$，$a_i \leq 10^4$ 左右（具体未明示，但双重循环可过）。
• 复杂度要求：当前解法时间复杂度 $O(n \cdot a_i)$，空间复杂度 $O(1)$。
• 算法知识点：暴力枚举、完全平方数、数学

思路解析

1. 数学建模：对于每个查询值 $x$，需判定是否存在正整数对 $(i, j)$ 满足 $i^2 + j^2 = x$。注意 $i, j \geq 1$（区别于非负整数）。
2. 枚举范围确定：由于 $i^2 \leq x$ 且 $j^2 \leq x$，可知 $i, j \in [1, \sqrt{x}]$。
3. 双重循环验证：外层枚举 $i$，内层枚举 $j$，计算平方和。一旦发现 $i^2 + j^2 = x$ 立即返回 true；若全部枚举完毕未找到，返回 false。
4. 关键细节：循环条件使用 pow(i, 2) <= x 控制上限，也可写作 i * i <= x（后者避免浮点精度风险）。

完整代码

#include <bits/stdc++.h>
using namespace std;

// 判定x是否能分解为两个正整数的平方和
bool check(int x) {
    // 枚举第一个数i，上界为sqrt(x)
    for (int i = 1; pow(i, 2) <= x; i++) {
        // 枚举第二个数j
        for (int j = 1; pow(j, 2) <= x; j++) {
            // 检查是否满足i² + j² = x
            if (i * i + j * j == x) {
                return true;  // 找到可行解立即返回
            }
        }
    }
    return false;  // 枚举完毕无解
}

int main() {
    int t;
    cin >> t;

    while (t--) {
        int x;
        cin >> x;
        if (check(x)) {
            cout << "Yes" << endl;
        }
        else {
            cout << "No" << endl;
        }
    }

    return 0;
}