luogu-B3957 [GESP202403 三级] 完全平方数

GESP三级真题，字符串和一维数组相关题目，难度★★☆☆☆。

luogu-B3957 [GESP202403 三级] 完全平方数

题目要求

题目描述

小杨同学有一个包含 $n$ 个非负整数的序列 $A$，他想要知道其中有多少对下标组合 $\langle i,j\rangle$（$1 \leq i < j \leq n$），使得 $A_i + A_j$ 是完全平方数。

如果 $x$ 是完全平方数，则存在非负整数 $y$ 使得 $y \times y = x$。

输入格式

第一行一个非负整数 $n$，表示非负整数个数。
第二入行包含 $n$ 个非负整数 $A_1, A_2, \dots A_n$，表示序列 $A$ 包含的非负整数。

输出格式

输出一行一个整数表示答案。

输入输出样例 #1

输入 #1

5
1 4 3 3 5

输出 #1

3

说明/提示

对全部的测试数据，保证 $1 \leq n \leq 1000$，$0 \leq A_i \leq 10^5$。

题目分析

解题思路

本题的解题思路如下：

1. 输入处理：

   • 读取序列长度n
   • 读取n个非负整数到数组中

2. 遍历处理：

   • 使用双重循环遍历所有可能的下标对(i,j)，其中i<j
   • 对于每对下标，计算对应元素之和
   • 判断该和是否为完全平方数：
     • 计算和的平方根
     • 检查平方根的平方是否等于原和

3. 结果统计：

   • 统计满足条件的下标对数量
   • 输出最终结果

复杂度分析：

• 时间复杂度：$O(n^2)$，其中n为序列长度
• 空间复杂度：$O(n)$，需要存储输入序列

{% include custom/custom-post-content-inner.html %}

示例代码

#include <cmath>
#include <iostream>

int main() {
    // 读取序列长度
    int n;
    std::cin >> n;
    
    // 创建数组并读入序列
    int ary[n];
    for (int i = 0; i < n; i++) {
        std::cin >> ary[i];
    }
    
    // 计数器，用于统计满足条件的下标对数量
    int count = 0;
    
    // 双重循环遍历所有可能的下标对
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            // 计算两数之和的平方根
            int sqr_i = std::sqrt(ary[i] + ary[j]);
            // 判断两数之和是否为完全平方数
            if (sqr_i * sqr_i == ary[i] + ary[j]) {
                count++;
            }
        }
    }
    
    // 输出结果
    std::cout << count;
    return 0;
}

{% include custom/custom-post-content-footer.md %}

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

“luogu-”系列题目可在 洛谷题库 在线评测。

“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP 认证学习微信公众号