题解 | 来点gcd

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define all(a) a.begin(), a.end()
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
using vi = vector<int>;
void solve() {
    int n, m;
    cin >> n >> m;
    vi a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    unordered_set<int> s(all(a)), ans;
    for (int d = 1; d <= n; d++) {
        int g = 0;
        for (int k = d; k <= n; k += d) {
            if (s.count(k)) {
                g = gcd(g, k);
            }
        }
        if (g == d) {
            ans.insert(d);
        }
    }
    while (m--) {
        int x; cin >> x;
        if (ans.count(x)) {
            yes;
        }
        else {
            no;
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int t = 1;
    cin >> t;
    for (int i = 1; i <= t; i++) {
        //cout << "----Test " << i << "----" << endl;
        solve();
    }
    return 0;
}

预处理枚举倍数