TaopiTTT

例題https://www.luogu.com.cn/problem/P10724

小性質：完全平方數的質因子出現數量應該為偶數，因此可以用異或去判斷是否為偶數

前綴異或和性質：
因為：\(a xor a=0\)，而且異或滿足交換律。
所以當前的前綴異或\(sxor\)之前出現過，說明中間的那些\(x\)都被抵消掉了，也就是中間子段的異或為0了。
如：5 = 5 xor 2 xor 3 xor 4 xor 2 xor 3 xor 4；

#include<bits/stdc++.h>
#define endl '\n'
#define lowbit(x) (x&-x)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const double pi=acos(-1);

int num[15]={2,3,5,7,11,13,17,19,23,29};
int n;

ll ck(int x){
    ll res=0;
    for(int i=0;i<10;i++){
        if(num[i]>x) break;
        while(x%num[i]==0){
            res^=(1<<i);
            x/=num[i];
        }
    }
    return res;
}

void solve(){
    cin>>n;
    vector<ll> pre(n+1);
    map<ll,ll> mp;
    ll ans=0;
    mp[0]=1;
    for(int i=1;i<=n;i++){
        cin>>pre[i];
        pre[i]=ck(pre[i])^pre[i-1];
        ans+=mp[pre[i]];
        mp[pre[i]]++;
    }
    cout<<ans<<endl;
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);
    int t=1;
    //cin>>t;
    while(t--) solve();
    return 0;
}