実装は軽め。
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の上限が大きくて一瞬びっくりする。