质因数分解+状态压缩求区间积

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

#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;
}