连通块

题面

小 X 有一张 $n$ 个节点的图，每个节点有一个点权。但让小 X 感到生气的是，这张图上并没有任何的边，于是他决定钦点一些边。

小 X 喜欢 gcd 和合数，所以小 X 的钦点规则与 gcd（最大公约数）和合数有关。具体来说，对于 $2$ 个点，如果它们点权的最大公约数为合数，那么 小 X 就会钦点它们之间连一条边。

小 Y 看到了小 X 幼稚的行为，决定把他批判一番。他知道小 X 热衷于连通块，因此他会删掉图中的一个点来使得剩余图中最大的连通块最小。

即将参加 NOIP2023 的你对这个问题很感兴趣，于是你想知道，在小 X 操作之后，图中剩余的最大连通块的大小是多少。

$n\leq10^5$ 。

题目大意

一张图，若点与点间点权最大公约数为合数则相连。现在求删除图中某点剩余的最大连通块的大小。

题解

喵喵题！

暴力建图 $\mathcal{O}(n^2)$ 考虑优化。如果两个点之间存在一条边，那么可以建一个虚拟节点（这个节点应是两个点的单位合数），向两个点连边，这跟原图在联通性上是等价的，其中单位合数为两个质数的乘积，数量为 $\mathcal{O}(\log^2V)$ 级别的， 其中 $V$ 是值域。如此把复杂度降到 $\mathcal{O}(n\log^2V)$ 。

然后并查集找最大和次大连通块，Tarjan 删最大连通块割点即可。

代码

const int N = 4e6 + 5, M = 1e7 + 5;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {
	int n;

	int pri[M], cnt, mn[M], id[M];
	bool vis[M];
	void Euler () {
		for (int i = 2; i < M; i++) {
			if (!vis[i]) pri[++cnt] = i, mn[i] = i;
			for (int j = 1; j <= cnt && i * pri[j] < M; ++j) {
				vis[i * pri[j]] = 1; mn[i * pri[j]] = pri[j];
				if (i % pri[j] == 0) break;
			}
		}
		cnt = 0;
		for (int i = 2; i < M; i++) if (vis[i] && !vis[i / mn[i]]) id[i] = ++cnt;
	}
	struct Edge {
		int nxt, to;
	} e[M];
	int head[N], tot = 1;
	void Add (int u, int v) {
		e[++tot] = (Edge) {head[u], v}, head[u] = tot;
	}

	int fa[N], sum[N];
	int Find(int k) {return k == fa[k]? fa[k]: fa[k] = Find(fa[k]);}
	void Merge (int u, int v) {
		int fu = Find(u), fv = Find(v);
		if (fu == fv) return;
		fa[fu] = fv; sum[fv] += sum[fu];
	}

	int mx, secm, maxp;
	void update (int val, int p) {
		if (val > mx) secm = mx, mx = val, maxp = p;
		else if (val > secm) secm = val;
	}

	int ans, all;

	int dfn[N], low[N], siz[N], cdfn;
	int st[N], top;
	void Tarjan (int u, int fat) {
		dfn[u] = low[u] = ++cdfn;
		st[++top] = u; siz[u] = 0;
		int ret = 0, flg = 0;
		for (int i = head[u]; i; i = e[i].nxt) {
			int v = e[i].to;
			if (v == fat) continue;
			if (!dfn[v]) {
				Tarjan(v, u); low[u] = min(low[u], low[v]);
				if (low[v] >= dfn[u]) flg++;
				if (low[v] > dfn[u]) top--, ret = max(ret, siz[v]), siz[u] += siz[v];
				else if (low[v] == dfn[u]) {
					int t, s = 0;
					do {
						t = st[top--];
						siz[u] += siz[t];
						s += siz[t];
					} while (t != v);
					ret = max(ret, s);
				}
			} else low[u] = min (low[u], dfn[v]);
		}
		if (u <= n) {
			siz[u]++;
			if ((fat && flg) || (!fat && flg > 1)) ans = min (ans, max(ret, all - siz[u]));
			else ans = min(ans, all - 1);
		}
	}
	int main () {
		Euler();
		for (int t = Read(); t--; ) {
			n = Read();
			for (int i = 1; i <= n + cnt; i++) fa[i] = i, sum[i] = i <= n;
			memset (dfn, 0, sizeof dfn); cdfn = top = 0; tot = 1;
			memset (head, 0, sizeof head);

			for (int i = 1; i <= n; i++) {
				int p[15] = {0}, c[15] = {0};
				int x = Read();
				while (x > 1) {
					int w = mn[x];
					p[++p[0]] = w;
					while (x % w == 0) c[p[0]] ++, x /= w;
				}
				for (int j = 1; j <= p[0]; j++) {
					for (int k = j + (c[j] <= 1); k <= p[0]; ++k) {
						if (1ll * p[j] * p[k] < M) {
							int v = id[p[j] * p[k]] + n;
							Add (i, v), Add (v, i);
							Merge(i, v);
						}
					}
				}
			}
			mx = 0, secm = 0, maxp = 0;
			for (int i = 1; i <= cnt + n; i++) {
				if (fa[i] != i || !sum[i]) continue;
				update(sum[i], i);
			}
			ans = all = mx;
			Tarjan (maxp, 0);
			printf ("%d\n", max(ans, secm));
		}
		return 0;
	}
}

int main () {
	freopen("connect.in", "r", stdin);
	freopen("connect.out", "w", stdout);
	Main::main();
	return 0;
}