算法分析

一、算法思想

该问题的核心是利用数论性质将子集存在性问题转化为整体GCD判定问题。

关键数学性质：对于询问值 x，令 Mₓ 表示原多重集 S 中所有 x 的倍数的集合。则存在 S 的非空子集使得其 GCD 等于 x，当且仅当 Mₓ 中所有元素的整体 GCD 恰好等于 x。

证明：

充分性：若 Mₓ 的整体 GCD 为 x，则 Mₓ 本身就是一个合法子集（所有元素都是 x 的倍数且整体 GCD 为 x）。
必要性：若 Mₓ 的整体 GCD g ≠ x，则 g 必为 x 的倍数且 g > x。由于 Mₓ 的任何子集的元素都是 g 的倍数，其子集 GCD 也必是 g 的倍数，不可能等于 x。

因此，问题转化为：对每个 x，快速计算 S 中所有 x 的倍数的整体 GCD。

二、算法步骤

预处理阶段

统计频次：读取 n 个元素后，建立计数数组 cnt[v]（1 ≤ v ≤ n），记录数值 v 在多重集中的出现次数。
构建 GCD 数组：创建数组 g[x]，表示所有 x 的倍数的整体 GCD。
- 遍历 x 从 1 到 n（顺序可逆）：
  - 初始化 g[x] = 0（表示暂未找到倍数）。
  - 枚举 x 的所有倍数 y = x, 2x, 3x, ... ≤ n：
    - 若 cnt[y] > 0，则执行 g[x] = gcd(g[x], y)（使用欧几里得算法）。
  - 若循环结束 g[x] 仍为 0，说明无 x 的倍数存在。

查询阶段

回答询问：对于每个查询值 x：
- 若 g[x] == x 输出 "YES"，否则输出 "NO"。

三、计算复杂度

时间复杂度

统计频次：O(n)
构建 GCD 数组：Σₓ₌₁ⁿ (n/x) = n·Hₙ = O(n log n)，其中 Hₙ 为调和级数。
处理 m 个查询：O(m)
每组数据总复杂度：O(n log n + m)

由于题目保证所有测试用例的 Σn ≤ 10⁶ 且 Σm ≤ 10⁶，最坏情况 T=1, n=10⁶ 时，运算量约为 2×10⁷ 次操作，配合 O(log n) 的 GCD 计算，总体高效可行。

空间复杂度

计数数组 cnt：O(n)
GCD 数组 g：O(n)
总空间复杂度：O(n)

四、代码实现

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;

    while (T--) {
        int n, m;
        cin >> n >> m;

        vector<int> cnt(n + 1, 0);
        int x;
        for (int i = 0; i < n; i++) {
            int a;
            cin >> a;
            cnt[a]++;
        }

        vector<bool> ans(n + 1, false);

        for (int i = 1; i <= n; ++i) {
            // 1. Calculate G = gcd of all multiples of i present in S.
            int g = 0;

            // Iterate through multiples: j = i, 2i, 3i, ...
            for (int j = i; j <= n; j += i) {
                if (cnt[j] > 0) {
                    g = gcd(g, j);

                    // Early break optimization (Crucial for performance)
                    if (g == i) {
                        break;
                    }
                }
            }

            // 2. Check the condition: Is the calculated GCD exactly equal to i?
            if (g == i) {
                ans[i] = true;
            }
        }

        // Answering M queries in O(1) each.
        while (m--) {
            int x;
            cin >> x;
            if (x <= n && ans[x]) {
                cout << "YES\n";
            } else {
                cout << "NO\n";
            }
        }
    }
}

题解 | #来点gcd#