思路比较明确，就是一个数，，如果和另外一个数乘起来是个平方数的话，那么满足一个条件
数A可以分解成为n1 个 a1,n2 个 a2 ……
数B可以分解成为m1个 a1,m2 个 a2……
这满足的条件是(ni + mi) % 2 == 0
一个数的分解出来奇个数的因子乘起来得到的值为v，找之前有几个数他的奇个数因子成积为v
代码如下：
#include<cmath>#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>using namespace std;typedef long long LL;const int maxv = 1000001;const int maxn = 100005;const int maxd = 1000005;int arr[maxn],vis[maxd];int pvis[maxd],prime[maxd],cnt = 0;void get_prime(){memset(pvis,0,sizeof(pvis));pvis[1] = 1;int m = sqrt(maxv);for(int i = 2; i <= m; i++)if(!pvis[i]){for(int j = i * i; j < maxv; j+= i)pvis[j] = 1;}for(int i = 2; i < maxv; i++)if(!pvis[i]){prime[cnt++] = i;}}int main(){int T;get_prime();scanf("%d",&T);while(T–){memset(vis,0,sizeof(vis));int n;scanf("%d",&n);for(int i = 0; i < n; i++)scanf("%d",&arr[i]);LL ans = 0;for(int i = 0; i < n; i++){int e = arr[i];int v = 1;for(int j = 0; j < cnt; j++){int c = 0;while(e % prime[j] == 0){e /= prime[j];c ++;}if(c & 1) v *= prime[j];if(!pvis[e] || e == 1) { v *= e; break;}}ans += vis[v];vis[v] ++;}printf("%lld\n",ans);}return 0;}
生气是拿别人做错的事来惩罚自己
