三级
C++ 算法考级专栏
🎨 视觉封面【GESP】C++三级真题 luogu-B3957 [GESP202403 三级] 完全平方数
GESP三级真题,字符串和一维数组相关题目,难度★★☆☆☆。
luogu-B3957 [GESP202403 三级] 完全平方数
题目要求
题目描述
小杨同学有一个包含 个非负整数的序列 ,他想要知道其中有多少对下标组合 (),使得 是完全平方数。
如果 是完全平方数,则存在非负整数 使得 。
输入格式
第一行一个非负整数 ,表示非负整数个数。
第二入行包含 个非负整数 ,表示序列 包含的非负整数。
输出格式
输出一行一个整数表示答案。
输入输出样例 #1
输入 #1
CONSOLE2 行
5
1 4 3 3 5输出 #1
CONSOLE1 行
3说明/提示
对全部的测试数据,保证 ,。
题目分析
解题思路
本题的解题思路如下:
-
输入处理:
- 读取序列长度n
- 读取n个非负整数到数组中
-
遍历处理:
- 使用双重循环遍历所有可能的下标对(i,j),其中i<j
- 对于每对下标,计算对应元素之和
- 判断该和是否为完全平方数:
- 计算和的平方根
- 检查平方根的平方是否等于原和
-
结果统计:
- 统计满足条件的下标对数量
- 输出最终结果
复杂度分析:
- 时间复杂度:,其中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 资源指引
所有代码开源上传至 GitHub:yummy-code 仓库 · GESP 专题站:GESP WIKI
🤝 技术交流与答疑
欢迎加入:C++ GESP/CSP 考级答疑群(688906745) 与 Java/Python交流群(982860385),点击可直接加群。
📚
猜你想读 · 相关文章推荐
GESP 编程与算法 · 三级⏱️ 4 分钟
【GESP】C++三级练习 luogu-B2110 找第一个只出现一次的字符
GESP三级练习,字符串和数组练习(C++三级大纲中5号知识点,一维数组和6号知识点,字符串),难度★★☆☆☆。
阅读全文 →
GESP 编程与算法 · 三级⏱️ 6 分钟
【GESP】C++三级真题 luogu-B3868 [GESP202309 三级] 进制判断
GESP三级真题,字符串和一维数组相关,难度★★☆☆☆。 luogu-B3868 [GESP202309 三级] 进制判断 题目要求 题目描述 N 进制数指的是逢 N 进一的计数制。例如,人们日常生活中大多使用十进制计数,而计算机底层则一般使用二进制。除此之外,八进制和...
阅读全文 →
GESP 编程与算法 · 三级⏱️ 4 分钟
【GESP】C++三级真题 luogu-B3956 [GESP202403 三级] 字母求和
GESP三级真题,字符串和一维数组相关题目,难度★★☆☆☆。 luogu-B3956 [GESP202403 三级] 字母求和 题目要求 题目描述 小杨同学发明了一种新型密码,对于每一个小写英文字母,该小写字母代表了一个正整数,即该字母在字母顺序中的位置,例如字母 a...
阅读全文 →
OneCoder
一个中年人的自留地,记录学习 C++、GESP/NOI、Java、Python 与算法架构的心得体会。本站唯一网址:coderli.com
读者讨论与留言
💬 还没有读者留言,快来成为第一个讨论者吧!

