AtCoder ABC #177 : E - Coprime

CSAcademyあったのか…。
https://atcoder.jp/contests/abc177/tasks/abc177_e

問題

正整数Aが与えられる。
以下のいずれであるか答えよ。

• どの2要素もGCDが1なら、pairwise coprime
• pairwise coprimeでなく全要素のGCDが1なら、setwise coprime
• どちらでもない

解法

setwise coprimeは全体のGCDを取るだけ。
あとはpairwise coprimeかどうかを判定しよう。
各値の登場回数を配列に記憶しておこう。
GCDがkとなる要素対があるかどうかは、kの倍数である要素が2個以上あるかどうか判定すればよい。
これは上記配列をk個毎に舐めて行けばよい。

int N;
int A[1010101];
int num[1010101];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	int g=0;
	FOR(i,N) {
		cin>>A[i];
		g=__gcd(g,A[i]);
		num[A[i]]++;
	}
	
	for(i=2;i<=1000000;i++) {
		x=0;
		for(j=i;j<=1000000;j+=i) x+=num[j];
		if(x>=2) break;
	}
	
	if(i==1000001) {
		cout<<"pairwise coprime"<<endl;
		return;
	}
	
	if(g==1) {
		cout<<"setwise coprime"<<endl;
	}
	else {
		cout<<"not coprime"<<endl;
	}
}

まとめ

ABCのEにしては簡単寄り？