G2011 [GESP202406 二级] 平方之和 题解

知识点：枚举、完全平方数、数学校验。

解题思路

枚举正整数x，计算b=a-x²；若b是正完全平方数，就存在另一正整数y使x²+y²=a。

为什么正确

所有合法x都小于√a，枚举覆盖全部分解；平方校验保证y确为整数。

易错点

x和y必须为正，不能把0²+a算进去；sqrt结果取整后还需验证y*y==b。

复杂度

每组时间O(√a)，空间O(1)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,a;
    cin>>n;
    while(n--) {
        cin>>a;
        bool ok=false;
        for(int x=1;x*x<a;x++) {
            int b=a-x*x,y=sqrt(b);
            if(y>0&&y*y==b)ok=true;
        }
        cout<<(ok?"Yes":"No")<<"\n";
    }
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用8个自行生成的测试点。