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:
, if there exists an edge whose both endpoints have degree ;
otherwise , if there exists at least one vertex of degree ;
otherwise .
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:
If each of them divides exactly one array element, the vertex is isolated.
If some prime divisor divides at least three array elements, the vertex has degree at least .
Otherwise, each prime divisor that appears in exactly two elements identifies one other neighbor. If all such divisors identify the same neighbor , the vertex has degree . If they identify different neighbors, its degree is at least .
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();
}