题解：P10724 [GESP202406 七级] 区间乘积

思路

看到 \(a_i\) 很小，不难想到状压一类的东西。考虑把每个数的质因数当做二进制位，这个二进制位的 \(1/0\) 代表含有这个质因数的奇偶，再做一个异或前缀和，显然完全平方数的质因子个数一定为偶数，根据异或的性质，两个相同的数异或才为 \(0\) 所以只需要找到异或前缀和中相同的数的个数就行了。

时间复杂度 \(O(n\sqrt n + n)\)

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 5;

int n,ans;

int a[N],prime[N],cnt,vis[N],dis[N],s[N];

void init(int M) {
	for(int i=2;i<=M;++i) {
		if(!vis[i]) prime[++cnt] = i;
		for(int j=1;j<=cnt;++j) {
			if(prime[j]*i>N) break;
			vis[prime[j]*i] = 1;
			if(i%prime[j]==0) break;
		}
	}
	for(int i=1;i<=cnt;++i) dis[i] = pow(2,i-1);
	return ;
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0) , cout.tie(0);
	cin>>n;
	init(31);
	for(int i=1;i<=n;++i) {
		cin>>a[i];
		for(int j=1;j<=cnt;++j) {
			int t = 0;
			while(a[i]%prime[j]==0) {
				a[i] /= prime[j];
				t++;
			}
			t%=2;
			s[i]+=t*dis[j];
		}
//		ans+=(sqrt(a[i])*sqrt(a[i])==a[i]);
		s[i]^=s[i-1];
		if(!s[i]) ans++;
	}
	sort(s+1,s+1+n);
	int res = 0;
	for(int i=1;i<=n;++i)
		if(s[i]==s[i+1]) res++;
		else ans += max(res*(res+1)/2,0LL),res = 0;
	cout<<ans<<"\n";
	return 0;
}