题解：CF2084B MIN = GCD

XsicAoPowerE · 2025-11-29 19:35:17 · 题解

前置知识

你需要懂得 \gcd 函数以及它的用法。

思路

这题可以用贪心来解决。

首先找出最小值为 minn，排序过后，minn的倍数肯定都在右边了，这时只要用 \gcd 找出 minn 的倍数的最大公因数记为 g，最后看 g 是否等于 minn。

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int a[N];
int main () {
    int T;
    cin >> T;
    while (T --) {
        int n;
        cin >> n;
        for (int i = 1;i <= n;i ++) {
            cin >> a[i];
        }
        int g = 0;
        sort (a + 1, a + n + 1);
        for (int i = 2;i <= n;i ++) {
            if (a[i] % a[1] == 0) g = __gcd (g, a[i]);
        }
        if (g == a[1]) cout << "Yes";
        else cout << "No";
        cout << endl;
    }
}