[GESP202406 二级] 平方之和

GESP二级真题，多层循环和分支练习，难度★✮☆☆☆。

luogu-B4002 [GESP202406 二级] 平方之和

题目要求

题目描述

小杨有 $n$ 个正整数 $a_1,a_2,\dots,a_n$，他想知道对于所有的 $i (1\le i\le n)$，是否存在两个正整数 $x$ 和 $y$ 满足 $x\times x+y \times y=a_i$。

输入格式

第一行包含一个正整数 $n$，代表正整数数量。 之后 $n$ 行，每行包含一个正整数，代表 $a_i$。

输出格式

对于每个正整数 $a_i$，如果存在两个正整数 $x$ 和 $y$ 满足 $x\times x+y \times y=a_i$，输出 Yes，否则输出 No。

输入 #1

2
5
4

输出 #1

Yes
No

说明/提示

对于第一个正整数，存在 $1\times 1+2 \times 2=5$，因此答案为 Yes。

对于全部数据，保证有 $1 \le n \le 10,1 \le a_i \le 10^6$。

题目分析

解题思路

1. 读取输入的正整数数量 $n$。
2. 遍历每个正整数 $a_i$。
3. 对于每个 $a_i$，初始化一个标志变量，用于标志是否找到满足条件的 $x$ 和 $y$。
4. 遍历可能的 $x$ 值，从 $1$ 到 $\sqrt{a_i}$。
5. 对于每个可能的 $x$ 值，计算可能的 $y$ 值：$y = \sqrt{a_i - x^2}$。
6. 如果 $y$ 是整数（即强转后，不丢失小数位，所以可以验证原等式）且不为 $0$，则标志变量为真，退出循环。
7. 根据标志变量的值，输出 Yes 或 No。

{% include custom/custom-post-content-inner.html %}

示例代码

#include <cmath>
#include <iostream>

using namespace std;
int main() {
    int n; // 输入的正整数数量
    cin >> n; // 读取输入的正整数数量
    int a1; // 每个正整数
    for (int i = 1; i <= n; i++) { // 遍历每个正整数
        cin >> a1; // 读取每个正整数
        bool flag = false; // 标志是否找到满足条件的x和y
        for (int k = 1; k * k < a1; k++) { // 遍历可能的x值
            double r = sqrt(a1 - k * k); // 计算可能的y值
            int d = (int)r; // 将y值转换为整数
            if (d * d + k * k == a1 && d != 0) { // 判断是否满足条件
                flag = true; // 如果满足条件，则标志为true
                break; // 并退出循环
            }
        }
        if (flag) { // 如果找到满足条件的x和y
            cout << "Yes" << endl; // 输出Yes
        } else { // 如果没有找到满足条件的x和y
            cout << "No" << endl; // 输出No
        }
    }
    return 0;
}

{% include custom/custom-post-content-footer.md %}

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

“luogu-”系列题目可在 洛谷题库 在线评测。

“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP 认证学习微信公众号