B4002 [GESP202406 二级] 平方之和

chen_zhe · 2025-03-18 11:56:22 · 题解

欢迎报名洛谷网校，期待和大家一起进步！

:::align{center} :::

本题考察循环嵌套。

首先我们使用一重循环读入正整数 a。对于每一个 a，我们有两种方式处理：

方法 1

使用二重循环，第一重循环枚举 x，第二重循环枚举 y，然后判断 x\times x+y\times y 是否与 a 相等。

使用这一种做法，需要做出优化：如果 x\times x 或者 y\times y 的结果大于 a，则后面的循环不必再进行了。例如说 a=102，此时若 y=10，10\times 10=100，11\times 11=121，再往后结果只会更大，不可能是答案。

找到解之后，使用布尔类型变量 flag 标记找到解，输出 Yes 并且退出两重循环。

参考代码：

bool flag = false; // 还未发现解
// 在循环条件中的 !flag，意思是如果 flag 为真，则不执行循环。
for (int x = 1; x * x <= a && !flag; x++) {
    for (int y = 1; y * y <= a && !flag; y++) {
        if (x * x + y * y == a) {
            flag = true; // 找到了一组解
            cout << "Yes" << endl;
        }
    }
}
// 无解情况输出 No

方法 2

实际上我们只需要循环枚举 x 即可。我们令 b=a-x^2。我们只需要判断 b 是否是完全平方数即可。

判断的方式是对 b 开根号得到的结果放入一个 int 类型变量 sqb 中，随后我们判断 sqb * sqb 是否等于 b。例如，\sqrt{2} \approx 1.414，转为 int 类型后是 1，而 1\times 1=1\neq 2，因此 \sqrt{2} 不是一个整数，因此 2 不是一个完全平方数。

参考代码：

for (int x = 1; x * x < a; x++) {
    int b = a - x * x;
    int sqb = sqrt(b);
    if (sqb * sqb == b) {
        cout << "Yes" << endl;
        flag = true;
        break;
    }
}
// 无解情况输出 No