寻找倍数

chen_zhe · 2024-07-03 18:43:34 · 题解

欢迎报名洛谷网校，期待和大家一起进步！

如果一个数能是序列中所有数的倍数，那么它一定是序列中的最大值。例如 [1,2,3,6] 中，6 是所有数的倍数，而且它是序列中的最大值。

倘若其不是序列中的最大值，假设它为 s，而序列中有一个更大的数 t，那么 s 显然不可能是 t 的正整数倍。

因此，我们要找到序列中的最大值 t，将其对每个 a_i 去试除，判断是否为每个 a_i 的倍数。如果存在 a_i 使得 t 不是 a_i 的倍数，则不存在，输出 No；否则存在，输出 Yes。

int t; cin >> t;
while (t--) {
    int n, maxa = 0;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        maxa = max(a[i], maxa);
    }
    bool flag = true;
    for (int i = 1; i <= n; i++) {
        if (maxa % a[i] != 0) {
            flag = false;
            break;
        }
    }
    if (flag) puts("Yes");
    else puts("No");
}