本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-06-18 09:05:36

这场 Div.2 CDEF 难度是反过来的。
本做法复杂度可能劣于正解，但是能过。

• 模拟样例。
  这个是倒数第二个样例：
  
  相同颜色圈住的数字代表相同连通块。
  容易发现，每个数组都构成了 $1$ 或 $2$ 条对角线。
  容易得出结论，左上角到右下角的对角线是由第一个元素组成，由此向左的每条对角线分别是第 $5,4,3,2$ 个元素构成的。
  由此向右的每条对角线分别是第 $2,3,4,5$ 个元素构成的。

• 结论
  注意除了 $1$ 号元素以外，所有元素都分别组成了 $2$ 条对角线，分别位于 $1$ 号元素对角线的左边和右边，为了方便，暂时称 $1$ 号元素对角线左边的对角线成为左对角线，右边同理。
  将下面所述 $1$ 号构成的左对角线和右对角线看作同一条对角线。
  由上述，第 $1,2,3,4,5$ 个元素组成的右对角线的依次相邻（前后距离为 $1$）。第 $1,5,4,3,2$ 个元素组成的左对角线依次相邻。
  形式化，$1,2,3,\cdots,n$ 个元素组成的右对角线前后距离为 $1$，另外 $1,n,n-1,\cdots,2$ 的前后距离也是 $1$。
  由于 $k \ge 2$，除了值为 $1$ 的元素，所有元素组成的单独一条对角线（左对角线和右对角线独立）都是同一个连通块。

• 做法
  问题是如何处理所有非互质的数对。
  看到 $a_i \le 10^6$，这个限制意味着可以在调和级数复杂度内预处理每个数的质因数，随后每个 testcase 只需要枚举所有出现过的质因数，并记录包含这个质因数的所有元素，按照上述规则建边就可以了，然后按照上述结论建边就可以了。
  最后 dfs 一遍求出连通块个数。

• 小细节
  值为 $1$ 的所有元素都是不同连通块，一个 $1$ 就能贡献 $n$ 个连通块，$1$ 应该被单独计算。

最后复杂度是一开始的预处理质因数，再加上每个测试数据的所有元素的质因数个数总和，大量 STL 的使用也不影响通过。

#include <bits\/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REP(i,a,b) for(int i=a;i>=b;i--)
#define pb push_back
#define mkpr make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
int T;
template<class T>
void ckmx(T& a,T b){
    a=max(a,b);
}
template<class T>
void ckmn(T& a,T b){
    a=min(a,b);
}
typedef vector<int> vi;
typedef vector<ll> vl;
#define fi first
#define se second 
template<class T>
T gcd(T a,T b){
    return !b?a:gcd(b,a%b);
}
template<class T>
T lcm(T a,T b){
    return a\/gcd(a,b)*b;
}
\/*1,2,3,4,5
5,1,2,3,4
4,5,1,2,3
3,4,5,1,2
2,3,4,5,1
可以注意到，从 1 形成的左上-右下对角线向左右延申，向左分别是 5,4,3,2 形成的。  
向右分别是 2,3,4,5 形成的。  
同一个对角线全部连接。  
1-5-4-3-2 或 1-2-3-4-5 对角线距离是 1   
本质上，可以枚举所有出现过的质因数，枚举这个质因数对应的所有元素。  
然后枚举所有相邻编号元素，单独处理 1 号对角线
考虑 1~1e6 所有数的质因数。
*\/
const int maxn=1e6+5;
int n,k,a[maxn];
vector<int> prims[maxn];
bool vis[maxn];
vector<int> div_to_elem[maxn];
vector<int> g[maxn*2];
void con(vi& ids){
	\/\/ ids 所有元素 gcd 不为 1，且按照元素 id 升序
	for(int& id:ids){
		if(id==1)continue;
		if(id-1+(n-id+1)<=k){
			g[id].emplace_back(id+n);
			g[id+n].emplace_back(id);
		}
	}
	if(ids.size()==1)return;
	\/\/for(int& id:ids)printf("id %d\n",id);
\/\/	puts("==========");
	for(int i=1;i<ids.size();i++){
		if(ids[i]-ids[i-1]<=k){
			g[ids[i]].emplace_back(ids[i-1]);
			g[ids[i-1]].emplace_back(ids[i]);
		\/\/	printf("con = z(%d) z(%d)\n",ids[i],ids[i-1]);
		}
	}
	if(ids.front()==1){
		reverse(ids.begin()+1,ids.end());
		for(int i=1;i<ids.size();i++){
			if((ids[i-1]==1?(n+1):ids[i-1])-ids[i]<=k){
				g[ids[i]+n].emplace_back(ids[i-1]+n);
				g[ids[i-1]+n].emplace_back(ids[i]+n);
			\/\/	printf("con = f(%d) f(%d)\n",ids[i],ids[i-1]);
			}
		}	
	}else{
		reverse(ids.begin(),ids.end());
		\/\/ mx,mx-1,...,mn
		if(n-ids.front()+1+ids.back()-1<=k){
			g[ids.front()+n].emplace_back(ids.back());
			g[ids.back()].emplace_back(ids.front()+n);
		}
		for(int i=1;i<ids.size();i++){
			if(((ids[i-1]==1?(n+1):ids[i-1]))-(ids[i])<=k){
				g[ids[i]+n].emplace_back(ids[i-1]+n);
				g[ids[i-1]+n].emplace_back(ids[i]+n);
			\/\/	printf("con = f(%d) f(%d)\n",ids[i],ids[i-1]);
			}
		}	
	}
}
bool dfsvis[maxn*2];
void dfs(int u){
	dfsvis[u]=1;
	for(int& v:g[u]){
		if(!dfsvis[v])dfs(v);
	}
}
void solve(){
	scanf("%d%d",&n,&k);
	ll ans=0;
	FOR(i,1,n){
		scanf("%d",&a[i]);
		if(a[i]==1){
			ans+=n;
		}
	}
	vector<int> divs;
	FOR(i,1,n){
		for(int& div:prims[a[i]]){
			if(!vis[div]){
				vis[div]=1;
				divs.emplace_back(div);
			}
			div_to_elem[div].emplace_back(i);
		}
	}
	if(a[1]!=1)g[1].emplace_back(n+1);
	for(int& div:divs){
		con(div_to_elem[div]);
	}
	
	FOR(i,1,2*n){
		if(a[((i>n)?(i-n):(i))]!=1&&!dfsvis[i]){
			ans++;
			dfs(i);
		}
	}
	printf("%lld\n",ans);
	\/\/ clear
	for(int& div:divs){
		vis[div]=0;
		div_to_elem[div].clear();
	}
	FOR(i,1,2*n){
		g[i].clear();
		dfsvis[i]=0;
	}
}
int main()
{
	FOR(i,2,1000000){
		if(prims[i].empty()==0)continue;
		for(int j=i;j<=1000000;j+=i){
			prims[j].emplace_back(i);
		}
	}
	scanf("%d",&T);
	while(T--){
		solve();
	}
	return 0;
}