Problem 1: Counting Valid Sets

In this problem, the floor operation does not affect the correcntess, so a brute-force DFS approach is applicable.

A critical observation: if the array contains the element \(1\), it must be skipped immediately. Otherwise, \(1\) could be selected infinitely many time, leading to incorrect results.

Solution Code

int power(int base, int exp) {
    int result = 1;
    while (exp > 0) {
        if (exp & 1) result = result * base;
        base = base * base;
        exp >>= 1;
    }
    return result;
}

int total, queries;
vector<int> elements;
unordered_map<int, int> visited;
int limit;
int count;

void search(int idx, int remaining) {
    if (idx == limit) {
        if (!visited[remaining]) {
            visited[remaining] = 1;
            count++;
        }
        return;
    }
    for (int p = 0; ; p++) {
        int val = power(elements[idx], p);
        if (val > remaining) break;
        search(idx + 1, remaining / val);
    }
}

signed main() {
    freopen("set.in", "r", stdin);
    freopen("set.out", "w", stdout);
    total = read(); queries = read();
    for (int i = 0; i < queries; i++) {
        elements.push_back(read());
    }
    sort(elements.begin(), elements.end());
    elements.erase(unique(elements.begin(), elements.end()), elements.end());
    limit = elements.size();
    if (elements[0] == 1) {
        search(1, total);
    } else {
        search(0, total);
    }
    if (!visited[0]) count++;
    cout << count;
    return 0;
}

Problem 2: GCD Subsequence Queries

The problem asks to find, for each query value, both the longest and shortest subsequence such that the GCD of the subsequence equals the query valuee.

The longest valid subsequence is trivially the entire array. The challenge lies in finding the shortest one.

A key insight: since \(2 \times 3 \times 5 \times 7 \times 11 \times 13 \times 17 \times 19 = 9699690 > w\), the length of any valid minimal subsequence cannot exceed \(7\).

Using inclusion-exclusion principle, we can enumerate the number of selected elements and subtract those where the GCD is a multiple of the target.

Solution Code

const int MOD = 1e9 + 7;

int modPower(int base, int exp) {
    int result = 1;
    while (exp > 0) {
        if (exp & 1) result = 1LL * result * base % MOD;
        base = 1LL * base * base % MOD;
        exp >>= 1;
    }
    return result;
}

int arr[MAXN], freq[MAXN];
int maxVal, minLen[MAXN], dp[MAXN];
int fact[MAXN], invFact[MAXN];

void precompute(int n) {
    fact[0] = 1; invFact[0] = 1;
    for (int i = 1; i <= n; i++) {
        fact[i] = 1LL * fact[i - 1] * i % MOD;
    }
    invFact[n] = modPower(fact[n], MOD - 2);
    for (int i = n - 1; i >= 1; i--) {
        invFact[i] = 1LL * (i + 1) * invFact[i + 1] % MOD;
    }
}

int comb(int n, int r) {
    if (n < r) return 0;
    return 1LL * fact[n] * invFact[r] % MOD * invFact[n - r] % MOD;
}

int n, m;

signed main() {
    n = read(); m = read();
    precompute(n);
    for (int i = 1; i <= n; i++) {
        arr[i] = read();
        freq[arr[i]]++;
        maxVal = max(maxVal, arr[i]);
    }
    for (int i = 1; i <= maxVal; i++) {
        for (int j = i * 2; j <= maxVal; j += i) {
            freq[i] += freq[j];
        }
    }
    for (int i = 1; i <= m; i++) minLen[i] = -1;
    for (int len = 7; len >= 1; len--) {
        for (int g = maxVal; g >= 1; g--) {
            dp[g] = comb(freq[g], len);
            for (int k = 2 * g; k <= maxVal; k += g) {
                dp[g] = (dp[g] - dp[k] + MOD) % MOD;
            }
        }
        for (int q = 1; q <= m; q++) {
            if (dp[q]) minLen[q] = len;
        }
    }
    for (int i = 1; i <= m; i++) {
        if (minLen[i] == -1) {
            cout << "-1 -1" << endl;
        } else {
            cout << minLen[i] << " " << freq[i] << endl;
        }
    }
    return 0;
}