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;
}