Codeforces #953 : Div2 F. Large Graph

よくこういう問題思いつくな。
https://codeforces.com/contest/1978/problem/F

問題

N要素の整数列Aと、2以上の正整数Kが与えられる。

まずN次正方行列Bを、Bの(0-originでの)r行目はAをr個右にrotateした値が入るものとする。
次にN^2頂点の無向グラフを考える。
B(i,j)に対応する点を(i,j)と呼ぶとき、2点(i,j)-(i',j')の間は、|i-i'|+|j-j'|がK以下かつGCD(B(i,j),B(i',j'))が2以上の時辺が張られる。

このグラフにおいて、連結成分は何個あるか求めよ。

解法

A[0]はBの対角成分に並び、それ以外の要素はB上で2か所斜めに配置される。
Kは2以上なので、A[i]!=1であれば、斜めに並んだ要素同士は連結される。
よってこの時点で2N-1個の連結成分に分かれる。

A[i]とA[j]を持つB上の要素は、|i-j|≦KかつGCD(A[i],A[j])なら連結になる。
よって(2N-1)個の各連結成分に対応する値を素因数分解し、同じ素因数を持つもの同士が行列内で距離K以内にあるか判定して連結していこう。

int T;
int N,K;
int A[2020202];
int C[2020202];
vector<int> cand[1<<20];

const int prime_max = 1000010;
vector<int> prime;
int NP,divp[prime_max];

template<int um> class UF {
	public:
	vector<int> par,rank,cnt,G[um];
	UF() {par=rank=vector<int>(um,0); cnt=vector<int>(um,1); for(int i=0;i<um;i++) par[i]=i;}
	void reinit(int num=um) {int i; FOR(i,num) rank[i]=0,cnt[i]=1,par[i]=i;}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int count(int x) { return cnt[operator[](x)];}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		cnt[y]=cnt[x]=cnt[x]+cnt[y];
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};
UF<2020202> uf;


void cprime() {
	if(NP) return;
	for(int i=2;i<prime_max;i++) if(divp[i]==0) {
		//M[i]=NP;
		prime.push_back(i); NP++;
		for(ll j=1LL*i*i;j>=i&&j<prime_max;j+=i) if(divp[j]==0) divp[j]=i;
	}
}

map<int,int> enumpr(int n) {
	map<int,int> V;
	
	while(divp[n]>1) {
		V[divp[n]]++;
		n/=divp[n];
	}
	if(n>1) V[n]++;
	return V;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cprime();
	
	cin>>T;
	while(T--) {
		vector<int> candp;
		cin>>N>>K;
		FOR(i,N) {
			cin>>x;
			if(i==0) {
				A[N-1]=x;
				C[N-1]=N;
			}
			else {
				A[N-1+i]=A[i-1]=x;
				C[N-1+i]=N-i;
				C[i-1]=i;
			}
		}
		uf.reinit(2*N-1);
		FOR(i,2*N-1) {
			auto p=enumpr(A[i]);
			if(p.size()) {
				FORR2(a,b,p) {
					cand[a].push_back(i);
					candp.push_back(a);
				}
				C[i]=1;
			}
		}
		sort(ALL(candp));
		FORR(p,candp) if(cand[p].size()) {
			FOR(i,cand[p].size()-1) if(cand[p][i+1]-cand[p][i]<=K) uf(cand[p][i],cand[p][i+1]);
			cand[p].clear();
		}
		ll ret=0;
		FOR(i,2*N-1) if(uf[i]==i) ret+=C[i];
		cout<<ret<<endl;
	}
}

まとめ

終わってみるとそこまで複雑でもないな。