CF1978F 题解
__vector__ · · 题解
这场 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;
}