//writer:Oier_szc

#include <bits/stdc++.h>
//#include <windows.h>
#define TS cerr<<"I AK IOI"<<endl;
#define cr(x) cerr<<x<<endl;
#define cr2(x,y) cerr<<x<<" "<<y<<endl;
#define cr3(x,y,z) cerr<<x<<" "<<y<<" "<<z<<endl;
#define int long long
using namespace std;
const int N=2e5+5,INF=2e9,mod=1145141919810114;
int n,maxn=0,ans=0;
int a[N],b[N],d[N];
int st[N],primes[N],len=0;
map<int,int> app;
signed main()
{
	srand(time(NULL));
	scanf("%lld",&n);
	for(int i=1;i<=2e5;++i) d[i]=1ll*rand()*rand();
	int x,cnt_0=0ll;
	for(int i=1;i<=n;++i)
	{
		scanf("%lld",&a[i]);
		if(!a[i]) 
		{
			++cnt_0;
			continue;
		}
		int cnt=0ll;
		for(int j=2;j<=a[i]/j;++j)
		{
			cnt=0ll;
			if(a[i]%j==0ll)
			{
				while(a[i]%j==0ll)
				{
					++cnt;
					a[i]/=j;
				}
				if(cnt&1ll) b[i]=b[i]^d[j];
			}
		}
		if(a[i]>1ll) b[i]=b[i]^d[a[i]];
		ans+=app[b[i]];
		app[b[i]]++;
	}
	printf("%lld\n",ans+cnt_0*(n-1ll)-cnt_0*(cnt_0-1ll)/2ll);
	return 0;
}

是这样的，如果1ll*rand()*rand()那里把1ll去掉就很容易被卡，但是加上基本稳过，求原因。