题解

题目解析

• 输入输出：第一行输入整数 $t$ 表示测试用例组数。每组测试用例包含两行：第一行为正整数 $n$，第二行为 $n$ 个正整数组成的序列。对于每组数据，输出 Yes 表示存在某个元素是序列中所有数的倍数，否则输出 No。
• 数据范围：$1 \le t \le 10$，$1 \le n \le 10^5$，$1 \le a_i \le 10^9$。注意多组数据总和可能达到 $10^6$ 量级。
• 复杂度要求：单组数据需要 $O(n)$ 时间处理，总时间复杂度 $O(t \cdot n) \le 10^6$，空间复杂度 $O(n)$。
• 算法知识点：数学观察、最大元素性质、整除判定

思路解析

1. 关键观察：若存在某个 $a_i$ 是序列中所有数的倍数，则 $a_i$ 必须是序列中的最大值。因为作为所有数的倍数，$a_i$ 必须满足 $a_i \ge a_k$ 对所有 $k$ 成立，故只能是最大值。
2. 验证策略：取出序列中的最大值 $\textit{max\_val}$，遍历检查 $\textit{max\_val}$ 是否能被序列中每一个数整除（即 $\textit{max\_val} \bmod a_k = 0$）。
3. 边界处理：当 $n=1$ 时，唯一元素自然是所有数（自身）的倍数，直接满足条件。
4. 复杂度分析：使用 max_element $O(n)$ 找最大值，再 $O(n)$ 验证整除性，单组数据复杂度 $O(n)$。

完整代码

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

const int MAXN = 1e5 + 10;  // 根据数据范围上限开数组

int arr[MAXN];

void solve() {
    int n;
    // 多组测试用例，清空数组避免残留数据干扰
    memset(arr, 0, sizeof(arr));
    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    // 找出最大值：只有最大值可能是"所有数的倍数"
    int max_val = *max_element(arr, arr + n);
    // 验证该最大值能否被所有数整除
    for(int i = 0; i < n; i++) {
        // 关键判断：若存在不能整除的情况（余数非0），则不存在满足条件的数
   
        if (max_val % arr[i] != 0) {  
            cout << "No" << endl;
            return;  // 提前退出，无需继续检查
        }
    }
    cout << "Yes" << endl;
}

int main() {
    int t;
    cin >> t;
    // 循环处理 t 组测试用例
    while(t--) solve();
    return 0;
}