Overview

This problem asks you to select \(2\) or more gems from \(N\) given gems to maximize the greatest common divisor (GCD) of their quality values, then find the minimum number of gems \(K\) needed to achieve that maximum GCD, and output the number of unused gems \(N - K\).

Let \(M\) be the maximum quality value. The determination of the maximum GCD \(G\) and the search for \(K\) using the inclusion-exclusion principle can be performed efficiently by combining modular hashing.

---

Analysis

1. Determining the Maximum GCD \(G\)

For the GCD of the selected gems to be \(g\), the quality values of all selected gems must be multiples of \(g\). Therefore, the largest \(g\) such that “there exist \(2\) or more multiples of \(g\) among \(A\)” is the maximum achievable beauty \(G\).

This can be found by scanning \(g = M, M-1, \ldots, 1\) in descending order from the maximum quality value \(M = \max(A_i)\), and counting “the number of multiples of \(g\) contained in \(A\)” for each \(g\). The first \(g\) for which this count is \(2\) or more is the desired \(G\).

2. Simplification of the Problem (Finding the Minimum Size \(K\) Such That GCD is 1)

Once the maximum GCD \(G\) is determined, we only need to consider gems whose quality values are multiples of \(G\). Let \(C_1, C_2, \ldots, C_m\) be the values obtained by dividing these gems’ quality values by \(G\).

The original problem can be rephrased as follows:

“Find the minimum \(k\) (call it \(K\)) such that we can select \(k\) elements from the sequence \(C\) with GCD equal to \(1\).”

This is because having a GCD of \(1\) after division means the GCD of the original quality values is exactly \(G\).

Concrete Example

For \(A = [12, 18, 30]\): 1. Multiples of \(g=6\) are \([12, 18, 30]\), which is \(3\) elements (\(2\) or more), so the maximum GCD is \(G = 6\). 2. Dividing these by \(G=6\) gives \(C = [2, 3, 5]\). 3. We consider the minimum number of elements to select from \(C\) to make the GCD equal to \(1\). - When \(k=2\), for example selecting \(\{2, 3\}\) gives \(\gcd(2, 3) = 1\), achieving a GCD of \(1\). - Therefore, the minimum count is \(K = 2\), and the answer is \(N - K = 3 - 2 = 1\).

3. Efficient Determination of the Minimum Size \(K\) for GCD to be 1

We increment \(k = 2, 3, \ldots\) and determine whether “there exists at least one combination of \(k\) elements from \(C\) with GCD equal to \(1\).”

Directly counting “the number of ways to select elements with GCD exactly \(1\)” is difficult, but it can be computed efficiently using the inclusion-exclusion principle (Möbius inversion formula).

Let \(cnt[x]\) be the number of elements in \(C\) that are multiples of \(x\). The number of combinations of selecting \(k\) elements from \(C\) such that their GCD is a multiple of \(x\) is \(\binom{cnt[x]}{k}\). By multiplying by the Möbius function \(\mu(x)\) and summing, the total number of combinations \(S_k\) where the GCD of the selected \(k\) elements is exactly \(1\) is:

\[S_k = \sum_{x=1}^{V} \mu(x) \binom{cnt[x]}{k}\]

(where \(V = \max(C)\))

The smallest \(k\) such that \(S_k > 0\) is the desired \(K\). However, since \(S_k\) can become extremely large, we perform modular arithmetic (double hashing) using appropriately large primes \(P_1, P_2\), and check whether \(S_k \not\equiv 0 \pmod{P_1}\) or \(S_k \not\equiv 0 \pmod{P_2}\), which allows correct determination while preventing hash collisions.

---

Algorithm

1. Create frequency array: Create an array count_A that records the occurrence count of each quality value \(A_i\).
2. Search for maximum GCD \(G\): Loop \(g\) from \(M\) down to \(1\), summing up the number of multiples of \(g\) using the harmonic series approach. The first \(g\) for which the count is \(2\) or more becomes \(G\).
3. Construct sequence \(C\): Divide elements of \(A_i\) that are multiples of \(G\) by \(G\) to form sequence \(C\). Let \(V = \max(C)\).
4. Create multiples counter cnt: For the elements of \(C\), compute how many multiples of each \(x \ (1 \le x \le V)\) exist using the harmonic series approach in \(O(V \log V)\), storing in cnt[x].
5. Compute the Möbius function: Precompute the Möbius function \(\mu(x)\) for \(1\) to \(V\) in \(O(V)\) using a linear sieve.
6. Search for minimum size \(K\): For \(k = 2, 3, \ldots\), compute \(S_k \pmod{P_1}\) and \(S_k \pmod{P_2}\). If either one is non-zero, then a selection of \(k\) elements with GCD \(1\) exists, so we set that \(k\) as \(K\) and terminate the search.

[Key Point] Regarding the search range of \(K\): any integer up to \(10^6\) has at most \(7\) distinct prime factors (since \(2 \times 3 \times 5 \times 7 \times 11 \times 13 \times 17 > 10^6\)). Therefore, the number of elements \(K\) needed to form a coprime group is bounded by a very small value (at most around \(7\)). Thus, the loop over \(k\) terminates after very few iterations.

---

Complexity

Let \(M = \max(A_i) \le 10^6\).

• Time complexity: \(O(M \log M)\)

  • Determining \(G\) takes \(O(M \log M)\) (harmonic series sum \(\sum \frac{M}{g} \approx M \log M\))
  • Computing the cnt array takes \(O(V \log V)\)
  • Computing the Möbius function takes \(O(V)\)
  • The search loop for \(K\) performs \(O(V)\) computation at each step. Since the number of iterations \(K\) can be treated as a constant (at most around \(7\)), this part is \(O(V)\), and the overall algorithm runs sufficiently fast in \(O(M \log M)\).

• Space complexity: \(O(M)\)

  • The arrays holding value frequencies and the Möbius function have size at most \(M\), leaving plenty of room within memory limits.

---

Implementation Notes

• Collision avoidance via double hashing: Since the combination count \(S_k\) can become extremely large, using modular arithmetic with only one prime may cause “false negatives (judging non-existence when it actually exists)” due to accidentally having \(S_k \equiv 0 \pmod P\). By using double hashing with two different primes such as \(10^9+7\) and \(10^9+9\), the probability of collision is effectively reduced to zero.

• Fast computation of binomial coefficients \(\binom{n}{k} \pmod P\): Since \(k\) is small, by precomputing the modular inverse of \(k!\) (inv_k_fact), we can efficiently compute \(\binom{n}{k}\) by simply multiplying the numerator terms in \(O(k)\).

  Source Code

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

long long power(long long base, long long exp, long long mod) {
    long long res = 1;
    base %= mod;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % mod;
        base = (base * base) % mod;
        exp /= 2;
    }
    return res;
}

long long modInverse(long long n, long long mod) {
    return power(n, mod - 2, mod);
}

long long nCr(long long n, int k, long long inv_k_fact, long long mod) {
    if (n < k) return 0;
    long long num = 1;
    for (int i = 0; i < k; ++i) {
        num = (num * ((n - i) % mod)) % mod;
    }
    return (num * inv_k_fact) % mod;
}

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

    int N;
    if (!(cin >> N)) return 0;

    vector<int> A(N);
    int max_A = 0;
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
        if (A[i] > max_A) max_A = A[i];
    }

    vector<int> count_A(max_A + 1, 0);
    for (int x : A) {
        count_A[x]++;
    }

    int G = 1;
    for (int g = max_A; g >= 1; --g) {
        int multiples = 0;
        for (int y = g; y <= max_A; y += g) {
            multiples += count_A[y];
        }
        if (multiples >= 2) {
            G = g;
            break;
        }
    }

    vector<int> C;
    for (int x : A) {
        if (x % G == 0) {
            C.push_back(x / G);
        }
    }

    int V = 0;
    for (int x : C) {
        if (x > V) V = x;
    }

    vector<int> count_C(V + 1, 0);
    for (int x : C) {
        count_C[x]++;
    }

    vector<int> cnt(V + 1, 0);
    for (int x = 1; x <= V; ++x) {
        for (int y = x; y <= V; y += x) {
            cnt[x] += count_C[y];
        }
    }

    vector<int> mu(V + 1, 0);
    vector<int> primes;
    vector<bool> is_prime(V + 1, true);
    mu[1] = 1;
    for (int i = 2; i <= V; ++i) {
        if (is_prime[i]) {
            primes.push_back(i);
            mu[i] = -1;
        }
        for (int p : primes) {
            if (i * p > V) break;
            is_prime[i * p] = false;
            if (i % p == 0) {
                mu[i * p] = 0;
                break;
            } else {
                mu[i * p] = -mu[i];
            }
        }
    }

    long long P1 = 1000000007;
    long long P2 = 1000000009;

    int K = -1;
    for (int k = 2; k <= (int)C.size(); ++k) {
        long long fact1 = 1, fact2 = 1;
        for (int i = 1; i <= k; ++i) {
            fact1 = (fact1 * i) % P1;
            fact2 = (fact2 * i) % P2;
        }
        long long inv_k_fact1 = modInverse(fact1, P1);
        long long inv_k_fact2 = modInverse(fact2, P2);

        long long sum1 = 0;
        long long sum2 = 0;
        for (int x = 1; x <= V; ++x) {
            if (mu[x] == 0) continue;
            long long term1 = nCr(cnt[x], k, inv_k_fact1, P1);
            long long term2 = nCr(cnt[x], k, inv_k_fact2, P2);
            if (mu[x] == 1) {
                sum1 = (sum1 + term1) % P1;
                sum2 = (sum2 + term2) % P2;
            } else {
                sum1 = (sum1 - term1 + P1) % P1;
                sum2 = (sum2 - term2 + P2) % P2;
            }
        }
        if (sum1 != 0 || sum2 != 0) {
            K = k;
            break;
        }
    }

    cout << N - K << "\n";

    return 0;
}

---

This editorial was generated by gemini-3.5-flash-thinking.