CCF-GESP 2024 年 3 月三级 C++ T2 完全平方数解题思路

1. 理解题目要求

我们先来看一下这道题的具体要求。题目给出一个包含 n 个非负整数的序列 A，要求统计其中有多少对下标组合 (i,j)（1≤i<j≤n），使得 A[i]+A[j] 是一个完全平方数。完全平方数的定义是：如果 x 是完全平方数，则存在非负整数 y 使得 y*y=x。

举个例子，当输入是 5 个数字 [1,4,3,3,5] 时，输出应该是 3。这是因为：

• 1+3=4（2 的平方）
• 1+3=4（另一个 1+3）
• 4+5=9（3 的平方）

这个题目看似简单，但要在考试中快速准确地解决，需要掌握一些技巧。我们先从最直观的暴力解法开始分析。

2. 暴力解法及其局限性

最直接的思路就是枚举所有可能的 (i,j) 对，然后检查它们的和是否是完全平方数。这就是所谓的暴力解法，代码实现起来也很简单：

#include <bits/stdc++.h>
using namespace std;

int a[1005];

int main() {
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    int ans = 0;
    for(int i = 1; i <= n; i++) {
        for(int j = i + 1; j <= n; j++) {
            int m = a[i] + a[j];
            int t = sqrt(m);
            if(t * t == m) ans++;
        }
    }
    cout << ans;
}

这个解法的时间复杂度是 O(n²)，因为有两层嵌套循环。对于 n=1000 的情况，最坏情况下需要执行约 50 万次循环（1000×999/2）。这在现代计算机上其实是可以接受的，因为题目给出的 n 上限是 1000。