OneCoder Avatar
OneCodercoderli.com · 1022 篇博文
三级

C++ 算法考级专栏

🎨 视觉封面

【GESP】C++三级真题 luogu-B3957 [GESP202403 三级] 完全平方数

📅 2025-05-17·✍️ OneCoder·计算中...·⏱️ 4 分钟

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

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

题目要求

题目描述

小杨同学有一个包含 个非负整数的序列 ,他想要知道其中有多少对下标组合 (),使得 是完全平方数。

如果 是完全平方数,则存在非负整数 使得 。

输入格式

第一行一个非负整数 ,表示非负整数个数。
第二入行包含 个非负整数 ,表示序列 包含的非负整数。

输出格式

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

输入输出样例 #1

输入 #1

CONSOLE2 行
5
1 4 3 3 5

输出 #1

CONSOLE1 行
3

说明/提示

对全部的测试数据,保证 ,。


题目分析

解题思路

本题的解题思路如下:

  1. 输入处理:

    • 读取序列长度n
    • 读取n个非负整数到数组中
  2. 遍历处理:

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

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

复杂度分析:

  • 时间复杂度:,其中n为序列长度
  • 空间复杂度:,需要存储输入序列

示例代码

C++33 行
#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;
}

看完题解去实战!OneCoder C++ 信奥远征闯关平台 (oi.coderli.com)
💡 OneCoder 资源指引

所有代码开源上传至 GitHub:yummy-code 仓库 · GESP 专题站:GESP WIKI

🤝 技术交流与答疑

欢迎加入:C++ GESP/CSP 考级答疑群(688906745) 与 Java/Python交流群(982860385),点击可直接加群。

📚

猜你想读 · 相关文章推荐

OneCoder

OneCoder

一个中年人的自留地,记录学习 C++、GESP/NOI、Java、Python 与算法架构的心得体会。本站唯一网址:coderli.com

读者讨论与留言

共 0 条讨论
邮箱必填 · 支持 Markdown 格式与直接回复
💬 还没有读者留言,快来成为第一个讨论者吧!