和上一题一样，把平方因子除去，然后对应的数就变成固定的

#include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;typedef long long LL;const int N=1e6+5;const int INF=0x3f3f3f3f;int vis[N],prime[1005],cnt;void getprime(){  bool v[1020];  memset(v,0,sizeof(v));  for(int i=2;i*i<=1000;++i){    if(v[i])continue;    for(int j=i*i;j<=1000;j+=i)      v[j]=1;  }  for(int i=2;i<=1000;++i)    if(!v[i])prime[++cnt]=i;}int main(){    int T,n;    getprime();    scanf("%d",&T);    while(T--){      memset(vis,0,sizeof(vis));      scanf("%d",&n);      LL ans=0;      for(int i=1;i<=n;++i){        int t;scanf("%d",&t);        for(int j=1;j<=cnt&&prime[j]<=t/prime[j];++j){            int tmp=0;            while(t%prime[j]==0)t/=prime[j],++tmp;            if(tmp&1)t*=prime[j];        }        ans+=vis[t];        // printf("%I64d\n",ans);        ++vis[t];      }      printf("%lld\n",ans);    }    return 0;}