由于$a_i$<=$30$,所以因数最大到$30$.前缀统计1~$i$的所有元素的质因数的和%$2$,用一个长度为$30$的字符串记录,并使用$map$($string$映射$int$)记录其数量.最后遍历1~$n$,利用之前的到的1~$i$所有质因子的和%$2$的前缀,统计器数量.由于每一对区间都会算两遍,所以还要统计1~$i$的乘积本身就是完全平方数的数量,这些不用除以二,其他的要除以二.这个思路很好想啊,只要学过$map$就可以. 代码:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n;
ll a[100010];
ll mp[100010][35];
map<string,ll>sum;
ll ans,ans_p;
void value(ll a,ll k){
	for(ll i=2;i<=a;i++){
		while(a%i==0){
			a/=i;
			mp[k][i]++;
			mp[k][i]%=2;
		}
	}
}
signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(ll i=1;i<=n;i++){
		cin>>a[i];
		for(ll j=2;j<=30;j++)
		mp[i][j]=mp[i-1][j];
		value(a[i],i);
		string str="";
		for(ll j=2;j<=30;j++){
			str+=(char)(mp[i][j]+'0');
		}
		sum[str]++;
	}
	for(ll i=1;i<=n;i++){
		string str="";
		ll p=0;
		for(ll j=2;j<=30;j++){
			str+=(char)(mp[i][j]+'0');
			if(mp[i][j]!=0)p=1;
		}
		if(!p)ans_p++;
		ans+=sum[str]-1;
	}
	cout<<ans_p+ans/2;
	return 0;
}

AC记录: https://www.luogu.com.cn/record/177912420