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

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

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

题目要求

题目描述

小杨有一个包含 $n$ 个正整数的序列 $A=[a_1,a_2,\dots,a_n]$，他想知道是否存在 $i(1\leq i\leq n)$ 使得 $a_i$ 是序列 $A$ 中所有数的倍数。

输入格式

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

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

其中，第一行包含一个正整数 $n$；第二行包含 $n$ 个正整数，代表序列 $A$。

输出格式

对于每组测试用例，如果存在 $i(1\leq i\leq n)$ ，满足对于所有 $k(1\leq k\leq n)$ $a_i$ 是 $a_k$ 的倍数，输出 Yes，否则输出 No。

输入输出样例 #1

输入 #1

2
3
1 2 4
5
1 2 3 4 5

输出 #1

Yes
No

说明/提示

【样例解释】:

对于第⼀组数据，对于 $a_3=4$，满足 $a_3$ 是 $a_1$ 和 $a_2$ 的倍数。

【数据范围】:

对于全部数据，保证有 $1\leq t\leq 10$，$1\leq n\leq 10^5$，$1\leq a_i\leq 10^9$。

---

题目分析

解题思路

本题有两种解题思路：

方法一：暴力枚举

1. 输入处理：
   • 读取测试用例数量t
   • 对每组测试用例，读取序列长度n和n个整数
2. 核心逻辑：
   • 遍历序列中的每个数a[i]
   • 检查a[i]是否是其他所有数的倍数
   • 如果找到一个满足条件的数，输出”Yes”并结束
   • 如果遍历完都没找到，输出”No”

复杂度分析：

• 时间复杂度：$O(n^2)$，需要两层循环遍历
• 空间复杂度：$O(n)$，需要存储n个数的数组

方法二：最大值判断

1. 输入处理：
   • 读取测试用例数量t
   • 对每组测试用例，读取序列长度n和n个整数
2. 核心逻辑：
   • 在读入数据时记录最大值
   • 只需检查最大值是否是所有其他数的倍数
   • 如果是则输出”Yes”，否则输出”No”

复杂度分析：

• 时间复杂度：$O(n)$，只需要一次遍历
• 空间复杂度：$O(n)$，需要存储n个数的数组

---

示例代码

方法一，暴力枚举

#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;
}

方法二 找最大值

#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;
}

---

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

GESP各级别考纲要点、知识拓展和练习题目清单详见C++学习项目主页

“luogu-”系列题目已加入洛谷Java、C++初学团队，作业清单，可在线评测，团队名额有限，欢迎加入。

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