Розв'язок
Побудуємо граф на вершинах: між та є ребро тоді й лише тоді, коли \gcd(a_i,a_j)>1. Величина масиву дорівнює кількості ребер графа. Видалення елемента відповідає видаленню вершини разом з усіма інцидентними ребрами.
Усі ізольовані вершини (степеня ) можна видалити без втрати ребер. Розглянемо, скільки ще вершин можна видалити, якщо дозволено втратити не більш ніж одне ребро.
Якщо видалена неізольована вершина, то кожне її ребро зникає. Отже, вона повинна мати степінь . Якщо видаляємо дві неізольовані вершини, всі зниклі ребра повинні збігатися з одним і тим самим ребром; отже, це мають бути два кінці ребра, обидва степеня . Видалити три або більше неізольованих вершин неможливо, бо тоді зникне принаймні два різні ребра.
Тому до кількості ізольованих вершин додаємо:
, якщо існує ребро, обидва кінці якого мають степінь ;
інакше , якщо існує хоча б одна вершина степеня ;
інакше .
Як знайти степені вершин
Перебирати всі пари елементів занадто повільно. Для кожного числа до A=3\cdot10^5 за допомогою решета попередньо знайдемо його різні прості дільники. Для кожного простого зберігатимемо список індексів елементів масиву, які діляться на .
Для вершини переглянемо прості дільники a_i:
Якщо кожен із них зустрічається рівно в одному елементі масиву, вершина ізольована.
Якщо деякий простий дільник зустрічається щонайменше в трьох елементах, степінь вершини принаймні .
Інакше кожен дільник, що зустрічається двічі, задає одного іншого сусіда. Якщо всі такі дільники задають того самого сусіда , степінь вершини дорівнює . Якщо вони задають різних сусідів, степінь принаймні .
Позначимо через єдиного сусіда вершини степеня , а для решти вершин покладемо to[i]=-1. Ребро з обома кінцями степеня існує тоді й лише тоді, коли для деякого виконується to[i]=j та to[j]=i.
Для a_i=1 множина простих дільників порожня, тому така вершина правильно вважається ізольованою.
Складність
Нехай — сумарна кількість різних простих дільників усіх елементів. Решето займає O(A\log\log A) часу. Побудова списків за допомогою map та їх обхід займають O(K\log A) часу. Оскільки для a_i\le3\cdot10^5 кількість різних простих дільників одного числа обмежена константою, для всіх наборів разом часова складність становить O(A\log\log A+\sum n\log A).
Пам'ять: O(A\log\log A+n+K), включно з попередньо обчисленими простими дільниками.
Реалізація C++17
#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();
}