三级
C++ 算法考级专栏
🎨 视觉封面【GESP】C++三级真题 luogu-B4004 [GESP202406 三级] 寻找倍数
GESP三级真题,一维数组相关题目,难度★★☆☆☆。
luogu-B4004 [GESP202406 三级] 寻找倍数
题目要求
题目描述
小杨有一个包含 个正整数的序列 ,他想知道是否存在 使得 是序列 中所有数的倍数。
输入格式
第一行包含一个正整数 ,代表测试用例组数。
接下来是 组测试用例。对于每组测试用例,一共两行。
其中,第一行包含一个正整数 ;第二行包含 个正整数,代表序列 。
输出格式
对于每组测试用例,如果存在 ,满足对于所有 是 的倍数,输出
Yes,否则输出No。
输入输出样例 #1
输入 #1
CONSOLE5 行
2
3
1 2 4
5
1 2 3 4 5输出 #1
CONSOLE2 行
Yes
No说明/提示
【样例解释】:
对于第⼀组数据,对于 ,满足 是 和 的倍数。
【数据范围】:
对于全部数据,保证有 ,,。
题目分析
解题思路
本题有两种解题思路:
方法一:暴力枚举
-
输入处理:
- 读取测试用例数量t
- 对每组测试用例,读取序列长度n和n个整数
-
核心逻辑:
- 遍历序列中的每个数a[i]
- 检查a[i]是否是其他所有数的倍数
- 如果找到一个满足条件的数,输出"Yes"并结束
- 如果遍历完都没找到,输出"No"
复杂度分析:
- 时间复杂度:,需要两层循环遍历
- 空间复杂度:,需要存储n个数的数组
方法二:最大值判断
-
输入处理:
- 读取测试用例数量t
- 对每组测试用例,读取序列长度n和n个整数
-
核心逻辑:
- 在读入数据时记录最大值
- 只需检查最大值是否是所有其他数的倍数
- 如果是则输出"Yes",否则输出"No"
复杂度分析:
- 时间复杂度:,只需要一次遍历
- 空间复杂度:,需要存储n个数的数组
示例代码
方法一,暴力枚举
C++45 行
#include <iostream>
int main() {
// 读取测试用例数量
int t;
std::cin >> t;
// 处理每组测试用例
for (int i = 0; i < t; i++) {
// 读取序列长度
int n;
std::cin >> n;
// 读取序列数据
int ary[n];
for (int j = 0; j < n; j++) {
std::cin >> ary[j];
}
// 标记是否找到符合条件的数
bool flag = false;
// 遍历每个数,检查是否是其他所有数的倍数
for (int j = 0; j < n; j++) {
// 计数器,记录当前数是多少个数的倍数
int count = 0;
// 检查当前数是否是其他每个数的倍数
for (int k = 0; k < n; k++) {
if (ary[j] % ary[k] == 0) {
count++;
} else {
// 如果不是某个数的倍数,直接跳出内层循环
break;
}
}
// 如果当前数是所有数的倍数
if (count == n) {
std::cout << "Yes" << std::endl;
flag = true;
break;
}
}
// 如果没有找到符合条件的数
if (!flag) {
std::cout << "No" << std::endl;
}
}
return 0;
}方法二 找最大值
C++35 行
#include <cmath>
#include <iostream>
int main() {
// 读取测试用例数量
int t;
std::cin >> t;
while (t--) {
// 读取序列长度
int n;
std::cin >> n;
// 定义数组并找出最大值
int ary[n];
int max_n = 0;
for (int i = 0; i < n; i++) {
std::cin >> ary[i];
max_n = std::max(max_n, ary[i]);
}
// 检查最大值是否是所有数的倍数
bool flag = true;
for (int i = 0; i < n; i++) {
if (max_n % ary[i] != 0) {
flag = false;
break;
}
}
// 输出结果
if (flag) {
std::cout << "Yes" << std::endl;
} else {
std::cout << "No" << std::endl;
}
}
return 0;
}💡 OneCoder 资源指引
所有代码开源上传至 GitHub:yummy-code 仓库 · GESP 专题站:GESP WIKI
🤝 技术交流与答疑
欢迎加入:C++ GESP/CSP 考级答疑群(688906745) 与 Java/Python交流群(982860385),点击可直接加群。
📚
猜你想读 · 相关文章推荐
GESP 编程与算法 · 三级⏱️ 4 分钟
【GESP】C++三级练习 luogu-B2064, 斐波那契数列
斐波那契数列本身可能并不一定涉及数组知识点,但本题中要求的输入、输出格式涉及到三级知识点一维数组的使用。 题目本身对小学生来说,也是有一定难度的。
阅读全文 →
GESP 编程与算法 · 三级⏱️ 4 分钟
【GESP】C++三级练习 luogu-B3661, [语言月赛202209] 排排队
三级知识点一维数组练习,除了应用了数组以外,其余逻辑比较简单,适合初学者。
阅读全文 →
GESP 编程与算法 · 三级⏱️ 3 分钟
【GESP】C++三级练习 luogu-B2087, 与指定数字相同的数的个数
GESP三级知识点一维数组练习,题目本身逻辑不复杂。 luogu-B2087 题目要求 题目描述 输出一个整数序列中与指定数字相同的数的个数。 输入格式 输入包含三行: 第一行为 n,表示整数序列的长度(n100); 第二行为 n 个整数,整数之间以一个空格分开; 第三...
阅读全文 →
OneCoder
一个中年人的自留地,记录学习 C++、GESP/NOI、Java、Python 与算法架构的心得体会。本站唯一网址:coderli.com
读者讨论与留言
💬 还没有读者留言,快来成为第一个讨论者吧!

