做法应该没有问题

但不知道为什么TLE on test 28

(CF1978F)[https://www.luogu.com.cn/problem/CF1978F]

(提交记录)[https://codeforces.com/contest/1978/submission/276855496]

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

const int N = 1e6 + 5;

int fa[N + N],prime[N],minp[N],a[N + N],lst[N];
bool vis[N];

int cntp = 0;

inline int get(int x)
{
	if (x == fa[x]) return x;
	return x = get(fa[x]);
} 

inline void merge(int x,int y)
{
	x = get(x),y = get(y);
	if (x != y) fa[x] = y;
}

inline void init()
{
	for (int i = 2;i <= N;i++)
	{
		if (!minp[i]) prime[++cntp] = i,minp[i] = i;
		for (int j = 1;j <= cntp && i * prime[j] <= N;j++)
		{
			minp[i * prime[j]] = prime[j];
			if (!(i % prime[j])) break;
		}
	}
}

vector < int > used;
long long ans = 0;

inline void solve()
{
	int n,k;
	cin >> n >> k;
	int nn = n + n;
	for (int i = n;i < nn;i++)
		cin >> a[i],a[i - n] = a[i];
	for (int i = 1;i < nn;i++)
		fa[i] = i;
	for (int i = 1;i < nn;i++)
	{
		int x = a[i];
		while (x != 1)
		{
			int d = minp[x],pre = lst[d];
			lst[d] = i;
			if (pre != 0 && i - pre <= k) merge(i,pre);
			while (!(x % d)) x /= d;
			if (!vis[d]) vis[d] = 1,used.push_back(d);
		}
	}
	for (int i = 1;i < nn;i++)
		if (a[i] == 1) ans += min(i,2 * n - i);
		else if (get(i) == i) ans++;
	for (auto i : used) vis[i] = 0,lst[i] = 0;
	used.clear();
	cout << ans << endl;
	ans = 0;
	return;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	init();
	int t;
	cin >> t;
	while (t--)	solve();
	return 0;
}