Codeforces Round 953 Div.2 F 题解

连通块计数的一种常见思路是钦定代表元，但发现这题的连边方式并不好指定一个代表元，那么只能尝试优化建图。

我们尝试观察一下连边的情况，通过手玩样例获得一些几何直观的感受：

3 4 5
5 3 4
4 5 3

这个样例也许比较小，不过你真的把边画出来就会发现：连边形如 \(2n-1\) 条完整的斜线，中间零散地连了一些边。

其实很有道理，斜线上相邻两个元素距离为 \(2\)，而 \(k\ge 2\)，故能形成连边。

然后我们只需要考虑斜线之间的连边。根据曼哈顿距离转切比雪夫距离的原理，我们发现，两条斜线之间的距离就是它们的编号之差。（表述可能不清，假设从左下到右上编号依次为 \(1,2,\dots,2n-1\)，那么 \(dis(i, j)=|i-j|)\)）。

于是我们只需要考虑序列上的情况。这是一个相对经典的问题，对于每个质数，分别维护最后一次出现的位置 \(lst_v\)，假设 \(v\) 是 \(a_i\) 的因子，且 \(i-lst_v\le k\)，连边 \((i,lst_v)\) 即可。时间复杂度 \(\mathcal O(n\log\log n)\)。不过我写的很粗糙，不是这个复杂度。

写完发现寄了，原因是没有考虑 \(1\) 没法形成斜线，因为 \(1\) 同样不会参与斜线之间的连边，直接特殊处理一下就行。

#include <bits/stdc++.h>
#define pb emplace_back
#define fir first
#define sec second
#define Tp template <typename T>

using i64 = long long;
using pii = std::pair<int, int>;

Tp T myabs(T x) { return x > 0 ? x : -x; }

constexpr int maxn = 1e6 + 5, N = 1e6;
int n, a[maxn << 1], k, pre[maxn << 1], lst[maxn];
std::vector<int> pr[maxn];

int find(int x) { return x == pre[x] ? x : pre[x] = find(pre[x]); }

void work() {
	std::cin >> n >> k;
	std::fill(a + 1, a + 2 * n, 0);
	for (int i = 1; i <= n; ++i) {
		std::cin >> a[n - 1 + i];
	}
	for (int i = 1; i < n; ++i) {
		a[n - i] = a[2 * n - i];
	}

	i64 ans = 0;
	for (int i = 1; i <= 2 * n - 1; ++i) {
		if (a[i] > 1) continue;
		ans += n - myabs(n - i) - 1;
	}

	std::iota(pre + 1, pre + 2 * n, 1);
	for (int i = 1; i <= 2 * n - 1; ++i) {
		for (auto& v : pr[a[i]]) {
			if (lst[v] && i - lst[v] <= k) {
				pre[find(i)] = find(lst[v]);
			}
			lst[v] = i;
		}
	}
	for (int i = 1; i <= 2 * n - 1; ++i) {
		for (auto& v : pr[a[i]]) {
			lst[v] = 0;
		}
	}

	int cnt = 0;
	for (int i = 1; i <= 2 * n - 1; ++i) {
		cnt += find(i) == i;
	}
	std::cout << (i64)cnt + ans << '\n';
	return;
}

int main() {
	std::cin.tie(nullptr)->sync_with_stdio(false);

	for (int i = 2; i <= N; ++i) {
		if (pr[i].empty()) {
			for (int j = i; j <= N; j += i) {
				pr[j].pb(i);
			}
		}
	}

	int t;
	std::cin >> t;
	while (t--) work();

	return 0;
}