判断序列中是否存在一个数,它是序列里所有数的倍数。多组测试。
给定包含 n 个正整数的序列 A。请判断是否存在下标 i,使得 aᵢ 是序列 A 中所有数的倍数。
本题包含多组测试数据。
整除判断最大值性质多组测试剪枝优化
| 项目 | 说明 |
|---|---|
| 输入 | 第一行 t;每组两行:n 和 n 个正整数 |
| 输出 | 每组一行 Yes 或 No |
| 数据范围 | t ≤ 10,n ≤ 10⁵ |
| 数值范围 | 1 ≤ aᵢ ≤ 10⁹ |
max % aₖ == 0,有一个不成立就输出 No样例答案依次是 Yes、No。
最大值 max = 4
检查 4 % 1 = 0 ✅
4 % 2 = 0 ✅
4 % 4 = 0 ✅
全部整除
✅ Yes(4 是 1、2、4 的倍数)
最大值 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) | 稳过 |
求 max,然后逐个检查 max % aₖ
对每个 aᵢ,检查它是否整除所有 aₖ
| 方案 | 单组复杂度 | n = 10⁵ 运算量 |
|---|---|---|
| 只试最大值 | O(n) | 约 2 × 10⁵ 次 |
| 枚举所有候选 | O(n²) | 约 10¹⁰ 次(超时) |
输入一个正整数序列,程序会取出最大值并逐个验证它能否整除所有数。
点按钮开始 →
#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 足够 |
写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
1 | Yes | 题面样例,4 是所有人的倍数 |
1 | No | 5 不能整除 2 |
1 | Yes | n = 1 时必然 Yes(唯一的数必是自身倍数) |
1 | No | 最大值 9,但 9 % 6 ≠ 0 |
1 | Yes | 全部相等时,任何数都是所有数的倍数 |
2 | Yes No | 多组数据,考察 max 是否重置 |
max % aᵢ == 0 吗?while (t--) 内部。unsigned:虽然本题用 0 或 -1 都可以(正数),但类型混用容易出意外。需要保存整组数据做第二轮验证,空间 O(n);如果想省空间,也可以把数据存起来后再验证(本题必须回头看,所以数组是必要的)。
✅ 最坏 10⁶ 次取模运算,瞬间完成;如果写成 O(n²) 则必然超时。
// 求最大值的正确初始化 int mx = 0; // 全是正数时可用 0 // int mx = a[0]; // 通用写法(可能有负数时用这个) // int mx = INT_MIN; // 也通用 // 整除判断 if (mx % a[i] == 0) { /* 能整除 */ } // 更一般的"候选唯一性"思路示例: // 求第二大值、判断某个数是否是唯一最大 等 // 都依赖于"先确定候选范围,再验证"的套路
把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。
| 能力点 | 本题怎么用 | 还能迁移到 |
|---|---|---|
| 最大值性质 | "是所有数的倍数" ⇒ 必为最大值 | 求众数候选、唯一性判断 |
| 候选剪枝 | 把 O(n²) 枚举缩成 O(n) | 所有"找满足条件元素"的题目 |
| 整除判断 | a % b == 0 | 因数、倍数、约数类题目 |