B4002 [GESP202406 二级] 平方之和

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

本题考察循环嵌套。

首先我们使用一重循环读入正整数

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 并且退出两重循环。

参考代码：

CPP

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

不是一个完全平方数。

参考代码：

CPP

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

B4002 [GESP202406 二级] 平方之和

文章操作

方法 1

方法 2

相关推荐

评论

B4002 [GESP202406 二级] 平方之和