Codeforces #694 Div1 B. Strange Definition

ちょっと気を抜くとすぐCodeforces側の記事作成の手が止まる…。
https://codeforces.com/contest/1470/problem/B

問題

• 正整数x,yが隣接するとは、LCM(x,y)/GCD(x,y)が平方数であることを意味する。
• 整数列Aの美しさとは、各要素において隣接する要素数の最大値を取ったものとする。
• f(A)は、Aの各要素を、Aと隣接する要素の積で置き換えたものとする。

整数列Aと、整数Wが与えられる。
f^W(A)の美しさを求めよ。

解法

Aの各要素を、事前に平方数で割れるだけ割っておく。
そうすると、美しさは最頻値の頻度ということになる。
また、f(A)を1回計算すると、頻度が偶数の要素は(再び平方数で割ると)1に置き換わるし、奇数の要素は(再び平方数で割ると)値が変わらない。
よって、fを2回以上適用しても、その美しさは変わらない。
そこでAとf(A)の美しさだけ求めておけばよい。

int T;
int N;
int A[303030];
int Q;
int G[1010101];
ll W;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	for(i=1;i<=1000000;i++) {
		G[i]=i;
	}
	for(i=2;i<=1000;i++) {
		x=i*i;
		for(y=x;y<=1000000;y+=x) while(G[y]%x==0) G[y]/=x;
	}
	
	cin>>T;
	while(T--) {
		map<int,int> M[3];
		cin>>N;
		FOR(i,N) {
			cin>>A[i];
			M[0][G[A[i]]]++;
		}
		
		FOR(i,2) {
			FORR(m,M[i]) {
				if(m.second%2==0) {
					M[i+1][1]+=m.second;
				}
				else {
					M[i+1][m.first]+=m.second;
				}
			}
		}
		int ma[3]={};
		FOR(i,3) {
			FORR(m,M[i]) ma[i]=max(ma[i],m.second);
		}
		
		cin>>Q;
		while(Q--) {
			cin>>W;
			if(W>=2) cout<<ma[2]<<endl;
			else cout<<ma[W]<<endl;
		}
	}
}

まとめ

見た目で一瞬びっくりする問題。