题解

题目解析

• 输入输出：第一行输入整数 $n$ 表示序列长度，第二行输入 $n$ 个非负整数。输出一个整数，表示满足 $1 \le i < j \le n$ 且 $A_i + A_j$ 为完全平方数的无序对 $(i,j)$ 的数量。
• 数据范围：$1 \le n \le 1000$，$0 \le A_i \le 10^5$。两数之和最大为 $2 \times 10^5$，在 32 位整数范围内。
• 复杂度要求：$n \le 1000$，双重循环最多约 $5 \times 10^5$ 次迭代，时间复杂度 $O(n^2)$ 符合 1s 限制；空间复杂度 $O(n)$ 用于存储数组。
• 算法知识点：暴力枚举、双重循环、完全平方数判定

思路解析

1. 枚举无序对：使用双重循环遍历所有满足 $i < j$ 的下标组合。外层循环 $i$ 从 $1$ 到 $n$，内层循环 $j$ 从 $i+1$ 到 $n$，确保每对只被统计一次且不重复。
2. 判定完全平方数：对于每对元素之和 $sum = A_i + A_j$，计算其整数平方根 $sq = \sqrt{sum}$。由于浮点数精度问题，不直接判断 $sq$ 是否为整数，而是通过验证 $sq \times sq$ 是否等于 $sum$ 来确认。若相等，则 $sum$ 是完全平方数，答案计数器加一。
3. 精度处理：使用 int sq = sqrt(sum) 截断取整后，通过乘法回验可避免因浮点精度导致的误判（如 $\sqrt{25}$ 可能存储为 $4.9999999$ 或 $5.0000001$）。

完整代码

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

int arr[1100];  // 存储序列，大小略大于1000防止越界

int main() {
    int n;
    cin >> n;
    int ans = 0;
    // 读入n个非负整数
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }
    // 双重循环枚举所有满足i<j的无序对
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            // 计算两数之和的整数平方根（向下取整）
            int sq = sqrt(arr[j] + arr[i]);
            // 关键验证：通过平方回验避免浮点精度误差
            // 若sq*sq等于原和，则说明原数是完全平方数
            if (sq * sq == arr[i] + arr[j]) ans++;
        }
    }
    cout << ans << endl;
    return 0;
}