GESP 题解库 / 3 级题解 / [GESP202403 三级] 完全平方数 · 第 16 / 28 题
GESP202403 三级 · B3957 · 入门

完全平方数

统计有多少对 (i, j)(i < j)满足 Aᵢ + Aⱼ 是完全平方数。

📊
n ≤ 1000
数据规模
🔢
Aᵢ ≤ 10⁵
数值范围
⚡
O(n²)
时间复杂度
🎯
枚举数对
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

给定含 n 个非负整数的序列 A,求有多少对下标组合 ⟨i, j⟩(1 ≤ i < j ≤ n)使得 Aᵢ + Aⱼ 是完全平方数。

如果 x 是完全平方数,则存在非负整数 y 使 y × y = x。

💡
人话翻译:两两配对(共 n(n−1)/2 对),把每对的和算出来,看它是不是某个整数的平方(如 0、1、4、9、16、25 …)。统计满足条件的对数。

🔍 关键词提取

枚举数对完全平方数判定浮点精度long long

已知条件

项目说明
输入第一行 n;第二行 n 个非负整数
输出满足条件的对数
数据范围1 ≤ n ≤ 1000
数值范围0 ≤ Aᵢ ≤ 10⁵
和的范围最大 2 × 10⁵,其平方根约 447

需要解决的问题

02
思维导图
整理解题思路的全貌
🔢 两两配对 + 平方判定
📥 读入
n 和 n 个数
用 long long 更稳
和可能到 2×10⁵
编号从 0 或 1 都行
🔁 枚举数对
外层 i 从 0 到 n−2
内层 j 从 i+1 到 n−1
保证 i < j 不重不漏
共 n(n−1)/2 对
✅ 判平方
s = (int)sqrt(x)
检查 s * s == x
必要时 s±1 再验一次
不要直接用 sqrt 比较
⚠️ 易错点
sqrt 浮点误差漏解
i、j 重复计数
忘记 0 也是完全平方数
int 溢出风险
03
样例手算推导
样例 5 个数,逐对检查

🧮 样例:A = [1, 4, 3, 3, 5],答案 3

n = 5,共有 5 × 4 / 2 = 10 对。我们逐对算和、判平方。

数对AᵢAⱼAᵢ + Aⱼ是否完全平方数
(1,2)145❌(2² = 4,3² = 9)
(1,3)134✅ 2² = 4
(1,4)134✅ 2² = 4
(1,5)156❌
(2,3)437❌
(2,4)437❌
(2,5)459✅ 3² = 9
(3,4)336❌
(3,5)358❌
(4,5)358❌
1
注意第 3、4 对

A 里有两个 3(下标 3 和 4)

它们和 1 配对都得到 4,所以要各算一次

答案是 3 对而不是 2 对

❗ 下标不同的相同数值要分别计数

🔑
为什么是"下标对"而不是"数值对"?题目说的是 ⟨i, j⟩ 下标组合,所以 A₃ = 3 与 A₄ = 3 是两个不同的元素,分别与 1 组成的数对要各算一次。写双重循环时天然满足这个要求。

🧮 关于 sqrt 的精度问题

直接比较 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,于是漏掉一个正确答案。正确做法是截断后用整数乘法回验。
04
解法对比
两重循环 vs 打平方表

⚔️ 解法对比

🟢 枚举数对 + 回验(推荐) 推荐

双重循环枚举所有数对,用 sqrt 截断后回验

  • 时间 O(n²)
  • n = 1000 时约 5 × 10⁵ 对
  • 不需要额外空间
  • 代码最直白
💡
为什么够用:n ≤ 1000 时总共约 50 万对,每对做一次 sqrt 和乘法,总运算量约 10⁶,完全够快。

🟠 先打平方数表

把 0 ~ 447 的平方预先算好放进数组,用标记数组 O(1) 判断

  • 判平方变成查表 O(1)
  • 总复杂度仍是 O(n²)
  • 节省的是常数因子
  • 代码略长
⚠️
什么时候值得:当 n 很大(如 10⁵,需要用更高级算法)或需要频繁判断时,打表会更快。本题规模小,直接算就够了。

📈 性能对比

方案判平方代价代码量
sqrt + 回验一次开方约 12 行
打平方表一次查表约 20 行
05
算法流程图
两层循环枚举数对
开始读入 n 和数组 Ai 从 0 枚举到 n − 2j 从 i + 1 枚举到 n − 1s = (int)sqrt(A[i] + A[j])s * s == A[i] + A[j] 吗?是 ✓ans 加 1否 ✗不计数输出 ans结束还有元素 → 继续枚举下一对
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🔢 完全平方数对数统计

输入一组非负整数,程序会枚举所有数对并标出哪些和是完全平方数。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码

#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,应该计数。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
5
1 4 3 3 5
3题面样例
2
1 3
1只有一对,1 + 3 = 4
2
1 2
01 + 2 = 3 不是完全平方数
2
0 0
10 是完全平方数(0 = 0 × 0)
3
0 1 3
20+1=1 ✅、0+3=3 ❌、1+3=4 ✅ → 共 2 对
3
1 1 1
02 不是完全平方数
✅
自查清单:① 内层循环从 i+1 开始吗?② 判平方用的是整数乘法回验吗?③ 0 的情况算对了吗?

🚨 易错点清单

⚠️
sqrt 精度漏解:必须截断后用整数乘法回验,必要时还要试 s±1。
⚠️
j 从 0 开始:会让每个数对被算两次,答案翻倍。正确的内层起点是 i + 1。
⚠️
忽略 0:0 是完全平方数,两个 0 相加得 0 应该计数。
⚠️
用 int 存和:本题最大 2 × 10⁵ 不会溢出,但如果数据放大就要用 long long。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(n²)
空间复杂度
O(n)
n 最大
1000
数对总数
约 5 × 10⁵

时间怎么算的?

空间都用在哪?

需要保存整个序列以便两两配对,空间 O(n)。

✅ 约 50 万对数、每次一次开方,总运算量 10⁶ 量级,轻松通过。

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 的题目
🌟
思考题:如果 n 放大到 10⁵,两重循环就超时了。能不能用"枚举平方数"反过来做?(提示:和的范围是 0 ~ 2 × 10⁵,完全平方数只有约 448 个。枚举每个平方数 S,把问题变成"有多少对之和等于 S",用哈希表统计每个值出现次数即可。)