kmjp's blog

競技プログラミング参加記です

yukicoder : No.2074 Product is Square ?

実装は軽め。
https://yukicoder.me/problems/no/2074

問題

10^18以下値を取る、N要素の正整数からなる数列A[i]が与えられる。
これらの積は平方数か判定せよ。

解法

値が大きいので、平方数で割っていく典型テクは使えない。
そこで、2要素(A[x],A[y])を総当たりし、G=gcd(A[x],A[y])でA[x],A[y]を割るという作業を繰り返そう。
この手順で全要素の積はG^2で割られることになるので、元のAの全要素の積が平方数かどうかには影響しない。

その後、Aの各要素は互いに素なので、各要素がそれぞれ平方数か判定すればよい。
これは単に平方根が整数か判定するだけ。

int T,N;
ll A[5050];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		FOR(i,N) cin>>A[i];
		FOR(y,N) FOR(x,y) {
			ll g=__gcd(A[x],A[y]);
			A[x]/=g;
			A[y]/=g;
		}
		ll ok=1;
		FOR(i,N) {
			ll r=0;
			for(j=30;j>=0;j--) if((r+(1<<j))*(r+(1<<j))<=A[i]) r+=1<<j;
			if(r*r!=A[i]) ok=0;
		}
		if(ok) {
			cout<<"Yes"<<endl;
		}
		else {
			cout<<"No"<<endl;
		}
	}
}

まとめ

Aの上限が大きくて一瞬びっくりする。