寻找倍数 题解

题目分析

我们需要判断序列 $A$ 中是否存在一个元素 $a_i$，满足 $a_i$ 是序列里所有数的倍数。换句话说，对于所有的 $a_k$，都有 $a_i \bmod a_k = 0$。

因为序列中的数都是正整数，所以满足条件的 $a_i$ 必须不小于序列中的任何一个数。否则，若存在某个 $a_k>a_i$，那么 $a_i$ 就不可能是 $a_k$ 的倍数。由此可知，符合条件的 $a_i$ 必定是序列的最大值。

因此问题转化为：检查序列的最大值是否能整除序列中的每一个数。

解题思路

对于每组测试数据：

1. 读取 $n$ 和序列 $A$，同时记录序列中的最大值 $M$。
2. 遍历序列，依次判断 $M \bmod a_i$ 是否等于 $0$。
3. 如果所有的 $a_i$ 都能被 $M$ 整除，则说明存在这样的 $i$（即最大值所在的位置），输出 Yes；否则输出 No。

算法说明

• 最大值 $M$ 可以通过一次循环求出。
• 判断整除性也只需一次循环，一旦发现某个 $a_i$ 不能被 $M$ 整除，就可以立即输出 No 并结束本组测试。
• 因为整数取模运算为 $O(1)$，所以整个算法是线性的。

时间复杂度分析

对于每组测试用例，我们需要 $O(n)$ 的时间找出最大值并进行整除检查。共有 $t$ 组数据，因此总时间复杂度为 $O(t \times n)$。题目中 $t \le 10$，$n \le 10^5$，可以轻松通过。

参考代码及解释

cpp
复制
1#include <bits/stdc++.h>
2using namespace std;
3
4const int N = 1e5 + 10;
5int a[N];
6
7int main() {
8    int t;
9    cin >> t;
10    while (t--) {
11        int n;
12        cin >> n;
13        int mx = 0;
14
15        // 读入序列并找出最大值
16        for (int i = 1; i <= n; i++) {
17            cin >> a[i];
18            mx = max(mx, a[i]);
19        }
20
21        bool bad = false;
22        // 检查最大值是否能整除所有数
23        for (int i = 1; i <= n; i++) {
24            if (mx % a[i] != 0) {
25                bad = true;
26                break;
27            }
28        }
29
30        if (bad)
31            cout << "No\n";
32        else
33            cout << "Yes\n";
34    }
35
36    return 0;
37}

代码解释

• mx 用于存放序列的最大值，在读入时同时更新。
• 利用一个布尔变量 bad 标记是否出现不整除的情况。
• 遍历数组时，如果发现 mx % a[i] != 0，说明最大值不是 $a_i$ 的倍数，直接置 bad = true 并跳出循环。
• 最后根据 bad 的值输出对应的答案。

该代码简洁高效，与题目分析中的思路完全一致。