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

C++ 算法考级专栏

🎨 视觉封面

【GESP】C++三级真题 luogu-B4004 [GESP202406 三级] 寻找倍数

📅 2025-05-19·✍️ OneCoder·计算中...·⏱️ 7 分钟

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

luogu-B4004 [GESP202406 三级] 寻找倍数

题目要求

题目描述

小杨有一个包含 个正整数的序列 ,他想知道是否存在 使得 是序列 中所有数的倍数。

输入格式

第一行包含一个正整数 ,代表测试用例组数。

接下来是 组测试用例。对于每组测试用例,一共两行。

其中,第一行包含一个正整数 ;第二行包含 个正整数,代表序列 。

输出格式

对于每组测试用例,如果存在 ,满足对于所有 是 的倍数,输出 Yes,否则输出 No。

输入输出样例 #1

输入 #1

CONSOLE5 行
2
3
1 2 4
5
1 2 3 4 5

输出 #1

CONSOLE2 行
Yes
No

说明/提示

【样例解释】:

对于第⼀组数据,对于 ,满足 是 和 的倍数。

【数据范围】:

对于全部数据,保证有 ,,。


题目分析

解题思路

本题有两种解题思路:

方法一:暴力枚举

  1. 输入处理:

    • 读取测试用例数量t
    • 对每组测试用例,读取序列长度n和n个整数
  2. 核心逻辑:

    • 遍历序列中的每个数a[i]
    • 检查a[i]是否是其他所有数的倍数
    • 如果找到一个满足条件的数,输出"Yes"并结束
    • 如果遍历完都没找到,输出"No"

复杂度分析:

  • 时间复杂度:,需要两层循环遍历
  • 空间复杂度:,需要存储n个数的数组

方法二:最大值判断

  1. 输入处理:

    • 读取测试用例数量t
    • 对每组测试用例,读取序列长度n和n个整数
  2. 核心逻辑:

    • 在读入数据时记录最大值
    • 只需检查最大值是否是所有其他数的倍数
    • 如果是则输出"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 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 格式与直接回复
💬 还没有读者留言,快来成为第一个讨论者吧!