G3008 [GESP202403 三级] 完全平方数 题解

知识点：双重枚举、完全平方数、计数。

解题思路

枚举下标对i<j，计算a[i]+a[j]，取整数平方根v并检查v*v是否等于该和。

为什么正确

每对不同下标恰枚举一次，平方校验恰判断这一对的和是否为完全平方数。

易错点

相同数值在不同位置仍是不同下标对；不要统计i==j。

复杂度

时间O(n²)，空间O(n)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<int>a(n);
    for(int &x:a)cin>>x;
    int ans=0;
    for(int i=0;i<n;i++)for(int j=i+1;j<n;j++) {
        int z=a[i]+a[j],v=sqrt(z);
        ans+=v*v==z;
    }
    cout<<ans;
}

说明

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