solution
\(a_i\) 和 \(a_j\) 在操作前后的乘积是不变的,也就是总乘积是固定的。最后要求所有的元素相同,那也就是说所有元素的乘积 \(total\) 一定满足 \(\sqrt[n]{total}\) 是整数。看了看数据范围没有办法直接乘起来,于是考虑分解质因数,最后看一下每个质因子的个数是否是四的倍数就可以了。
赛时代码,比较丑陋
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
#include<utility>
#include<vector>
#include<queue>
#include<bitset>
#include<map>
#define FOR(i,a,b) for(register int i=a;i<=b;i++)
#define ROF(i,a,b) for(register int i=a;i>=b;i--)
#define mp(a,b) make_pair(a,b)
#define pll pair<long long,long long>
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
inline int read();
typedef long long ll;
typedef double db;
const int N=1e4+5;
const int MAXN=1e6+5;
const int INF=0x3f3f3f3f;
int n,m,k;
int tot=0,prime[MAXN+5],cntp=0,isp[MAXN+5];
map<int,int>c;
void init(){
FOR(i,1,MAXN) isp[i]=1;
isp[1]=0;
FOR(i,2,MAXN){
if(isp[i]) prime[++cntp]=i;
for(int j=1;j<=cntp&&i*prime[j]<=MAXN;j++){
isp[i*prime[j]]=0;
if(i%prime[j]==0) break;
}
}
}
int main()
{
int T=read();
init();
while(T--){
n=read();
tot=0;
c.clear();
FOR(i,1,n){
k=read();
FOR(j,1,cntp){
if(k==1) break;
if(k%prime[j]==0){
c[prime[j]]++;
k/=prime[j];
while(k%prime[j]==0&&k!=1)
c[prime[j]]++,k/=prime[j];
}
}
}
int f=0;
for(auto v:c){
if(v.se%n!=0){
puts("NO");
f=1;
break;
}
}
if(!f) puts("YES");
}
return 0;
}
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return f*x;
}