统计有多少对 (i, j)(i < j)满足 Aᵢ + Aⱼ 是完全平方数。
给定含 n 个非负整数的序列 A,求有多少对下标组合 ⟨i, j⟩(1 ≤ i < j ≤ n)使得 Aᵢ + Aⱼ 是完全平方数。
如果 x 是完全平方数,则存在非负整数 y 使 y × y = x。
枚举数对完全平方数判定浮点精度long long
| 项目 | 说明 |
|---|---|
| 输入 | 第一行 n;第二行 n 个非负整数 |
| 输出 | 满足条件的对数 |
| 数据范围 | 1 ≤ n ≤ 1000 |
| 数值范围 | 0 ≤ Aᵢ ≤ 10⁵ |
| 和的范围 | 最大 2 × 10⁵,其平方根约 447 |
int s = sqrt(x); 后检查 s * s == xsqrt 返回浮点数,结果可能差 1,要截断后再回代验证n = 5,共有 5 × 4 / 2 = 10 对。我们逐对算和、判平方。
| 数对 | Aᵢ | Aⱼ | Aᵢ + Aⱼ | 是否完全平方数 |
|---|---|---|---|---|
| (1,2) | 1 | 4 | 5 | ❌(2² = 4,3² = 9) |
| (1,3) | 1 | 3 | 4 | ✅ 2² = 4 |
| (1,4) | 1 | 3 | 4 | ✅ 2² = 4 |
| (1,5) | 1 | 5 | 6 | ❌ |
| (2,3) | 4 | 3 | 7 | ❌ |
| (2,4) | 4 | 3 | 7 | ❌ |
| (2,5) | 4 | 5 | 9 | ✅ 3² = 9 |
| (3,4) | 3 | 3 | 6 | ❌ |
| (3,5) | 3 | 5 | 8 | ❌ |
| (4,5) | 3 | 5 | 8 | ❌ |
A 里有两个 3(下标 3 和 4)
它们和 1 配对都得到 4,所以要各算一次
答案是 3 对而不是 2 对
❗ 下标不同的相同数值要分别计数
直接比较 sqrt(x) == (int)sqrt(x) 是有风险的,我们用一个具体例子说明。
| 检查方式 | 代码 | 结果 |
|---|---|---|
| 错误写法 | if (sqrt(x) == (int)sqrt(x)) | 浮点误差可能让 9 算成 2.9999999 |
| 正确写法 | int s = (int)sqrt(x); if (s * s == x) | ✅ 用整数乘法回验 |
| 更保险 | for (s-1; s+1; s++) if (s*s == x) | 容忍 ±1 的误差,最稳 |
sqrt 返回 double,像 9、16 这种数在某些实现下可能返回 2.9999999999999996,直接 (int) 截断就变成 2,平方后是 4 ≠ 9,于是漏掉一个正确答案。正确做法是截断后用整数乘法回验。双重循环枚举所有数对,用 sqrt 截断后回验
把 0 ~ 447 的平方预先算好放进数组,用标记数组 O(1) 判断
| 方案 | 判平方代价 | 代码量 |
|---|---|---|
| sqrt + 回验 | 一次开方 | 约 12 行 |
| 打平方表 | 一次查表 | 约 20 行 |
输入一组非负整数,程序会枚举所有数对并标出哪些和是完全平方数。
点按钮开始 →
#include <bits/stdc++.h> using namespace std; long long a[1005]; int main() { int n; scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%lld", &a[i]); long long ans = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { // j 从 i+1 开始,保证 i < j 且不重复 long long sum = a[i] + a[j]; long long s = (long long)sqrt((double)sum); // 回验 ±1,彻底规避浮点误差 if (s * s == sum) ans++; else if ((s + 1) * (s + 1) == sum) ans++; else if (s > 0 && (s - 1) * (s - 1) == sum) ans++; } } printf("%lld\n", ans); return 0; }
j 从 i + 1 开始?这样每对 ⟨i, j⟩ 只会被检查一次,既满足题目要求的 i < j,又不会重复计数。如果 j 从 0 开始,同一对会被算两次。| 代码 | 作用 | 为什么这样写 |
|---|---|---|
for (j = i + 1; ...) | 枚举数对 | 保证 i < j,且每对只算一次 |
(long long)sqrt((double)sum) | 开平方 | 截断取整,避免浮点直接比较 |
s * s == sum | 回验 | 用整数乘法验证,是判平方的正确姿势 |
(s±1) * (s±1) == sum | 误差兜底 | 容忍 sqrt 差 1 的情况,最保险 |
sqrt(x) == (int)sqrt(x) 判断,可能因浮点误差漏解;② j 从 0 开始,导致每对重复计数(答案翻倍);③ 忽略 0 也是完全平方数(0 = 0 × 0),当两个数都是 0 时和是 0,应该计数。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
5 | 3 | 题面样例 |
2 | 1 | 只有一对,1 + 3 = 4 |
2 | 0 | 1 + 2 = 3 不是完全平方数 |
2 | 1 | 0 是完全平方数(0 = 0 × 0) |
3 | 2 | 0+1=1 ✅、0+3=3 ❌、1+3=4 ✅ → 共 2 对 |
3 | 0 | 2 不是完全平方数 |
i + 1。需要保存整个序列以便两两配对,空间 O(n)。
✅ 约 50 万对数、每次一次开方,总运算量 10⁶ 量级,轻松通过。
// 判断完全平方数的三种写法 bool isSquare1(long long x) { long long s = (long long)sqrt((double)x); return s * s == x || (s + 1) * (s + 1) == x; } bool isSquare2(long long x) { // 完全避免浮点 long long s = 0; while (s * s < x) s++; return s * s == x; // 慢,但绝对准确 } bool isSquare3(long long x, const vector<char> &mark) { return x < (long long)mark.size() && mark[x]; // 打表查 } // 打平方表(适合值域不大的情况) const int MAXV = 200005; vector<char> sqMark(MAXV, 0); for (long long i = 0; i * i < MAXV; i++) sqMark[i * i] = 1;
把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。
| 能力点 | 本题怎么用 | 还能迁移到 |
|---|---|---|
| 枚举数对 | j = i+1 起,不重不漏 | 所有两两配对、组合计数题 |
| 完全平方数判定 | sqrt 截断 + 整数回验 | 平方数、立方数判定 |
| 浮点误差防范 | 用整数运算回验结果 | 所有涉及 sqrt、pow 的题目 |