思路与算法

先筛最小质因子。将每个ai分解，列出其中每个指数至少2的p²以及任意两个不同质因子的乘积pq。为每个实际出现的特征数建立一个辅助顶点，原顶点与自己的所有特征相连。辅助点权0，原点权1。这样原图中的一个同特征完全团变成辅助星，不显式枚举二次方边。对二部图做迭代DFS和Tarjan low计算，子树权为其含原顶点数。对原顶点u，凡DFS孩子v满足low[v]>=dfn[u]，删u后该孩子子树独立成块，记录其权最大值与权总和；剩余同连通块部分大小为总原点数-1-分离权总和。再与删点所在连通块之外的最大块比较，即是删u后的最大连通块。所有原顶点取最小。

正确性说明

正整数gcd为合数当且仅当至少含某个p²，或至少含两个不同素数p、q，因此原图相邻当且仅当两点共有一个辅助特征。辅助星替代完全团保持原顶点间的全部连通关系；删任意原点后这一等价仍成立，辅助点不计人数。Tarjan条件low[v]>=dfn[u]精确表示孩子子树不能绕过u到达u上方，所以这些子树在删u后分别断开；其他未分离部分都通过祖先或返祖边连在一起。权值按原点计数，因此得到的每块大小恰为原图人数。独立原连通块不受删u影响，用全局最大/次大连通块人数补足，枚举所有原点便得最优删除方案。

复杂度

设A=max ai，E为一个数据组中所有原点-特征连接数，F为不同特征数。最小质因子线性筛初始化O(A)时间、O(A)空间，只对一个输入文件做一次；读取T组共O(Σn)空间。每个数最多8种不同质因子，列举特征O(Σω(ai)²+Σlog ai)。构图、CSR和所有Tarjan数组初始化及迭代DFS为O(n+F+E)，本组空间O(n+F+E)，另加筛、特征编号表O(A)。同一输入的总时间再对T组上述主项求和。

易错点

共享一个质因子p不够，gcd=p仍是素数；重复的素数值也不能自动合并。必须同时考虑p²与pq两种合数特征。只允许删原点，不能把零权辅助点当候选。low分离后剩余部分要减去被删原点的1，其他连通块也必须参与最大值。深图使用显式栈，辅助顶点只按原点数量计权。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    vector<vector<int>> input(T);
    int A = 2;
    for (auto &a : input) {
        int n;
        cin >> n;
        a.resize(n);
        for (int &v : a) {
            cin >> v;
            A = max(A, v);
        }
    }
    vector<int> spf(A + 1), pr;
    for (int x = 2; x <= A; x++) {
        if (!spf[x]) {
            spf[x] = x;
            pr.push_back(x);
        }
        for (int p : pr) {
            if (p > spf[x] || 1ll * x * p > A)
                break;
            spf[x * p] = p;
        }
    }
    vector<int> id(A + 1, -1);
    for (auto &a : input) {
        int n = a.size(), N = n;
        vector<pair<int, int>> edges;
        vector<int> used;
        for (int u = 0; u < n; u++) {
            int x = a[u];
            vector<int> p, square;
            while (x > 1) {
                int z = spf[x], cnt = 0;
                while (x % z == 0) {
                    x /= z;
                    cnt++;
                }
                p.push_back(z);
                if (cnt >= 2)
                    square.push_back(z * z);
            }
            for (int i = 0; i < (int)p.size(); i++)
                for (int j = 0; j < i; j++)
                    square.push_back(p[i] * p[j]);
            for (int f : square) {
                if (id[f] < 0) {
                    id[f] = N++;
                    used.push_back(f);
                }
                edges.emplace_back(u, id[f]);
            }
        }
        vector<int> start(N + 1);
        for (auto e : edges) {
            start[e.first + 1]++;
            start[e.second + 1]++;
        }
        for (int i = 1; i <= N; i++)
            start[i] += start[i - 1];
        vector<int> to(start[N]), at = start;
        for (auto e : edges) {
            to[at[e.first]++] = e.second;
            to[at[e.second]++] = e.first;
        }
        vector<int> dfn(N), low(N), par(N, -1), it = start, weight(N), sep(N), mx(N), component(n);
        vector<int> totals;
        int timer = 0;
        for (int s = 0; s < N; s++)
            if (!dfn[s]) {
                int ci = totals.size();
                vector<int> st(1, s), original;
                dfn[s] = low[s] = ++timer;
                weight[s] = s < n;
                if (s < n)
                    original.push_back(s);
                while (!st.empty()) {
                    int u = st.back();
                    if (it[u] < start[u + 1]) {
                        int v = to[it[u]++];
                        if (v == par[u])
                            continue;
                        if (!dfn[v]) {
                            par[v] = u;
                            dfn[v] = low[v] = ++timer;
                            weight[v] = v < n;
                            if (v < n)
                                original.push_back(v);
                            st.push_back(v);
                        } else
                            low[u] = min(low[u], dfn[v]);
                    } else {
                        st.pop_back();
                        int p = par[u];
                        if (p >= 0) {
                            weight[p] += weight[u];
                            low[p] = min(low[p], low[u]);
                            if (low[u] >= dfn[p]) {
                                sep[p] += weight[u];
                                mx[p] = max(mx[p], weight[u]);
                            }
                        }
                    }
                }
                totals.push_back(weight[s]);
                for (int u : original)
                    component[u] = ci;
            }
        int best1 = 0, best2 = 0, count1 = 0;
        for (int x : totals)
            if (x > best1) {
                best2 = best1;
                best1 = x;
                count1 = 1;
            } else if (x == best1)
                count1++;
            else
                best2 = max(best2, x);
        int ans = n;
        for (int u = 0; u < n; u++) {
            int whole = totals[component[u]],
                other = (whole == best1 && count1 == 1) ? best2 : best1;
            int v = max({mx[u], whole - 1 - sep[u], other});
            ans = min(ans, v);
        }
        cout << ans << '\n';
        for (int f : used)
            id[f] = -1;
    }
}