12980.完全平方数

题目大意

给定一个长度为 $n$ 的非负整数序列 $A$，统计满足以下条件的下标对 $(i,j)$ 的数量：

• $1\le i<j\le n$
• $A_i + A_j$ 是一个完全平方数（即存在非负整数 $y$ 使得 $y^2 = A_i + A_j$）

思路分析

本题的数据范围较小：$n \leq 1000$，$A_i \leq 10^5$。两个数的和最大为 $2 \times 10^5$，其平方根不超过 $447$。我们完全可以使用最直接的方法：枚举所有的下标对 $(i,j)$，判断它们的和是否为完全平方数。

判断一个整数 $m$ 是否为完全平方数的常见方法是：利用 sqrt 函数取整，再验证平方是否等于原数。但由于浮点运算存在精度误差，直接取整可能导致误判。例如，当 $m$ 是完全平方数时，sqrt(m) 可能因精度问题略小于真实平方根，强制类型转换后 t * t < m。参考代码中使用 sqrt(m + 1e-7) 加上一个极小的正数，可以有效避免这种误差，保证取整后得到真实的平方根。

算法说明

1. 读入 $n$ 和数组 $A$。
2. 初始化答案计数器 ans = 0。
3. 双重循环枚举所有满足 $i<j$ 的下标对 $(i,j)$：
   • 计算两数之和 $m = A_i + A_j$。
   • 计算 $t = \lfloor \sqrt{m + 10^{-7}} \rfloor$。
   • 如果 $t \times t = m$，则 ans 加 $1$。
4. 输出 ans。

如果不想使用浮点数，可以用整数二分查找平方根，但在本题数据范围下浮点写法简单且安全。

时间复杂度分析

• 双重循环枚举所有对，共有 $\frac{n(n-1)}{2}$ 种组合，时间复杂度为 $O(n^2)$。
• 每次判断完全平方数调用 sqrt，是常数时间 $O(1)$。
• $n \leq 1000$ 时，最大枚举次数约为 $5 \times 10^5$，在 $1$ 秒内完全可以轻松运行结束。

空间复杂度分析

数组存储 $n$ 个整数，空间复杂度 $O(n)$。

参考代码及解释

cpp
复制
1#include <bits/stdc++.h>
2using namespace std;
3
4const int N = 1010;
5int a[N];
6
7int main() {
8    int n;
9    cin >> n;
10    for (int i = 1; i <= n; i++) {
11        cin >> a[i];
12    }
13
14    int ans = 0;
15    for (int i = 1; i <= n; i++) {
16        for (int j = i + 1; j <= n; j++) {
17            int m = a[i] + a[j];
18            // 加一个小量 1e-7 避免浮点误差导致 sqrt 所得整数偏小
19            int t = sqrt(m + 1e-7);
20            if (t * t == m) {
21                ans++;
22            }
23        }
24    }
25    cout << ans << "\n";
26    return 0;
27}

代码细节说明

• sqrt(m + 1e-7)：加上 $10^{-7}$ 的作用是修正可能的精度损失。当 $m$ 为完全平方数时，sqrt(m) 的计算结果可能为 $y - \epsilon$，取整后会变成 $y-1$，导致误判。加上一个很小的正数后，取整结果正确地指向 $y$。
• t * t == m：用整数的平方与原始和进行严格相等比较，确保判断的准确性。
• 循环中 $j$ 从 $i+1$ 开始，保证 $i<j$，避免重复计数。