An Almost Unchanged Value#13123

An Almost Unchanged Value (Editorial)

Solution

Construct a graph with vertices, where an edge exists between vertices and if and only if \gcd(a_i,a_j)>1. The value of the array is equal to the number of edges in this graph. Removing an element corresponds to removing a vertex along with all its incident edges.

All isolated vertices (vertices of degree ) can be removed without losing any edges. Let us determine how many additional vertices can be removed if we are allowed to lose at most one edge.

If a non-isolated vertex is removed, all its incident edges disappear. Therefore, it must have degree . If we remove two non-isolated vertices, all removed edges must be the same single edge. Thus, these vertices must be the endpoints of an edge, both having degree . Removing three or more non-isolated vertices is impossible, since at least two distinct edges would disappear.

Therefore, we add the following to the number of isolated vertices:

Finding the degrees of vertices

Checking all pairs of elements would be too slow. Using a sieve, we precompute the distinct prime divisors of every number up to A=3\cdot10^5. For each prime , we maintain a list of indices of array elements divisible by .

For each vertex , consider the prime divisors of a_i:

Let denote the only neighbor of a vertex of degree , and set to[i]=-1 for all other vertices. An edge whose both endpoints have degree exists if and only if there is some such that to[i]=j and to[j]=i.

For a_i=1, the set of prime divisors is empty, so such a vertex is correctly considered isolated.

Complexity

Let be the total number of distinct prime divisors across all array elements. The sieve takes O(A\log\log A) time. Building and processing the lists using map takes O(K\log A) time. Since each number a_i\le3\cdot10^5 has only a constant number of distinct prime divisors, the total time complexity over all test cases is O(A\log\log A+\sum n\log A).

The space complexity is O(A\log\log A+n+K), including the precomputed prime divisors.

C++17 Implementation

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

const int maxn = 3e5 + 10;
vector<int> primes[maxn];

void sieve() {
    for (int i = 2; i < maxn; i++) {
        if (primes[i].empty()) {
            for (int j = i; j < maxn; j += i)
                primes[j].push_back(i);
        }
    }
}

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int &x : a) cin >> x;

    map<int, vector<int>> idx;
    for (int i = 0; i < n; i++) {
        for (int p : primes[a[i]])
            idx[p].push_back(i);
    }

    vector<int> to(n, -1);
    int ans = 0;

    for (int i = 0; i < n; i++) {
        int neighbor = -1;
        bool bad = false;

        for (int p : primes[a[i]]) {
            if (idx[p].size() > 2) {
                bad = true;
                break;
            }
            if (idx[p].size() == 2) {
                int j = (idx[p][0] == i ? idx[p][1] : idx[p][0]);
                if (neighbor != -1 && neighbor != j) {
                    bad = true;
                    break;
                }
                neighbor = j;
            }
        }

        if (!bad && neighbor == -1) ans++;
        if (!bad && neighbor != -1) to[i] = neighbor;
    }

    bool found_one = false, found_two = false;
    for (int i = 0; i < n; i++) {
        if (to[i] == -1) continue;
        found_one = true;
        if (to[to[i]] == i) found_two = true;
    }

    if (found_two) ans += 2;
    else if (found_one) ans++;
    cout << ans << '\n';
}

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

    int t;
    cin >> t;
    while (t--) solve();
}