GESP 题解库 / 3 级题解 / [GESP202406 三级] 寻找倍数 · 第 14 / 28 题
GESP202406 三级 · B4004 · 简单

寻找倍数

判断序列中是否存在一个数,它是序列里所有数的倍数。多组测试。

📊
n ≤ 10⁵
数据规模
🔢
aᵢ ≤ 10⁹
数值范围
⚡
O(n)
每组时间
🎯
只看最大值
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

给定包含 n 个正整数的序列 A。请判断是否存在下标 i,使得 aᵢ 是序列 A 中所有数的倍数。

本题包含多组测试数据。

💡
人话翻译:要找一个"老大",它得能被序列里每一个数整除。注意是"是所有数的倍数",不是"与某个数成倍数关系"。

🔍 关键词提取

整除判断最大值性质多组测试剪枝优化

已知条件

项目说明
输入第一行 t;每组两行:n 和 n 个正整数
输出每组一行 Yes 或 No
数据范围t ≤ 10,n ≤ 10⁵
数值范围1 ≤ aᵢ ≤ 10⁹

需要解决的问题

02
思维导图
整理解题思路的全貌
🔍 只看最大值这一个候选
📥 读入
读 n 和序列
同时记录最大值 max
用 long long 存
数组可省
🧠 关键推理
若 x 是所有数的倍数
则 x ≥ 每个数
所以 x 只能是最大值
候选唯一 → 只试一个
✅ 验证
对每个 aₖ 检查 max % aₖ == 0
有一个不整除就 No
全部整除就 Yes
O(n) 完成
⚠️ 易错点
枚举所有候选导致 O(n²) 超时
把"是某个数的倍数"当成条件
n = 1 时必然 Yes
多组数据忘了重置 max
03
样例手算推导
样例两组对比验证

🧮 样例两组:为什么只看最大值就够

样例答案依次是 Yes、No。

1
第 1 组:[1, 2, 4]

最大值 max = 4

检查 4 % 1 = 0 ✅

4 % 2 = 0 ✅

4 % 4 = 0 ✅

全部整除

✅ Yes(4 是 1、2、4 的倍数)

2
第 2 组:[1, 2, 3, 4, 5]

最大值 max = 5

5 % 1 = 0 ✅

5 % 2 = 1 ❌ ← 已经失败了

(后面 5 % 3、5 % 4 也不用再看)

❌ No

🔑 关键推理:候选只有最大值一个

"x 是所有数的倍数"意味着对每个 aₖ 都有 x % aₖ == 0,也就是 x ≥ aₖ。既然 x 不小于序列中的任何一个数,x 就必须是最大值(最大值本身也是唯一的候选身份)。

思路候选个数复杂度结果
枚举每个 aᵢ 当候选n 个O(n²)n = 10⁵ 时超时
只试最大值1 个O(n)稳过
🔑
这个推理的价值:把 O(n²) 直接降到 O(n),而且推理只用到一个最朴素的性质——"倍数不会比原数小"。很多优化都是从这种朴素的单调性质来的。
04
解法对比
只试最大值 vs 枚举所有候选

⚔️ 解法对比

🟢 只试最大值(推荐) 推荐

求 max,然后逐个检查 max % aₖ

  • 每组 O(n)
  • 一遍求 max、一遍验证
  • 不需要存整个数组
  • 推理清晰、代码极短
💡
额外好处:因为不需要回头看旧数据,可以边读边求 max,第二遍再验证(或者干脆存数组)。

🟠 枚举每个元素当候选

对每个 aᵢ,检查它是否整除所有 aₖ

  • 每组 O(n²)
  • n = 10⁵ 时约 10¹⁰ 次
  • t = 10 时彻底超时
  • 而且大部分候选一看就不可能
⚠️
注意:其实在暴力枚举时也能加"必须是最大值"的剪枝,但那就等价于正解了——不如直接写成正解。

📈 性能对比

方案单组复杂度n = 10⁵ 运算量
只试最大值O(n)约 2 × 10⁵ 次
枚举所有候选O(n²)约 10¹⁰ 次(超时)
05
算法流程图
求最大值 → 逐个验证整除
开始读入 t读入 n 和序列,求出最大值 maxk 从 1 到 n,检查 max % aₖ存在某个 aₖ 不能整除 max 吗?是 ✗标记不满足否 ✓继续检查检查结果如何?全部整除输出 Yes有一个不整除输出 Not 组都处理完了吗?结束还有测试组 → 继续
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🔍 倍数查找器

输入一个正整数序列,程序会取出最大值并逐个验证它能否整除所有数。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码

#include <bits/stdc++.h>
using namespace std;

int a[100005];

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int n;
        scanf("%d", &n);

        int mx = 0;                      // 元素都是正整数,从 0 开始取最大安全
        for (int i = 0; i < n; i++) {
            scanf("%d", &a[i]);
            if (a[i] > mx) mx = a[i];
        }

        bool ok = true;
        for (int i = 0; i < n; i++) {
            if (mx % a[i] != 0) { ok = false; break; }
        }

        printf("%s\n", ok ? "Yes" : "No");
    }
    return 0;
}
🔑
为什么 mx 可以初始化为 0?题目保证 aᵢ 都是正整数(≥ 1),所以 0 一定比它们都小,不会成为错误的"最大值"。如果数据里可能有负数,就必须改用 a[0] 初始化。

📖 关键几行怎么看

代码作用为什么这样写
if (a[i] > mx) mx = a[i];求最大值边读边更新,不用第二次遍历求 max
mx % a[i] != 0整除判断余数为 0 说明能整除
break;提前退出发现一个不满足就可以定 No,省时间
int mx类型选择aᵢ ≤ 10⁹ 未超 int 上限,int 足够
⚠️
两个坑:① 枚举所有元素当候选,写出 O(n²) 导致超时;② 理解错题意——题目要的是"是所有数的倍数",不是"与某个数存在倍数关系"。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
1
3
1 2 4
Yes题面样例,4 是所有人的倍数
1
5
1 2 3 4 5
No5 不能整除 2
1
1
7
Yesn = 1 时必然 Yes(唯一的数必是自身倍数)
1
3
6 3 9
No最大值 9,但 9 % 6 ≠ 0
1
4
1 1 1 1
Yes全部相等时,任何数都是所有数的倍数
2
3
1 2 4
3
2 3 6
Yes
No
多组数据,考察 max 是否重置
✅
自查清单:① 只检查了最大值吗?② max 每组重置了吗?③ 判断用的是 max % aᵢ == 0 吗?

🚨 易错点清单

⚠️
枚举所有候选:写出 O(n²),n = 10⁵ 时超时。要利用"候选只能是最大值"这个推理。
⚠️
多组数据忘记重置 max:第二组的 max 会继承上一组的值,结果全错。必须写在 while (t--) 内部。
⚠️
把 mx 初始化为 -1 却又用 unsigned:虽然本题用 0 或 -1 都可以(正数),但类型混用容易出意外。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(t × n)
空间复杂度
O(n)
t 最大
10
n 最大
10⁵

时间怎么算的?

空间都用在哪?

需要保存整组数据做第二轮验证,空间 O(n);如果想省空间,也可以把数据存起来后再验证(本题必须回头看,所以数组是必要的)。

✅ 最坏 10⁶ 次取模运算,瞬间完成;如果写成 O(n²) 则必然超时。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 求最大值的正确初始化
int mx = 0;                     // 全是正数时可用 0
// int mx = a[0];              // 通用写法(可能有负数时用这个)
// int mx = INT_MIN;           // 也通用

// 整除判断
if (mx % a[i] == 0) { /* 能整除 */ }

// 更一般的"候选唯一性"思路示例:
// 求第二大值、判断某个数是否是唯一最大 等
// 都依赖于"先确定候选范围,再验证"的套路

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
最大值性质"是所有数的倍数" ⇒ 必为最大值求众数候选、唯一性判断
候选剪枝把 O(n²) 枚举缩成 O(n)所有"找满足条件元素"的题目
整除判断a % b == 0因数、倍数、约数类题目
🌟
思考题:如果题目改成"是否存在一个数是所有数的因数",候选该是谁?(提示:因数不会比原数大,所以候选也只能是最小值——把"最大值"换成"最小值"即可,推理完全对称。)