Untitled

mail@pastecode.io avatar
unknown
plain_text
5 days ago
1.2 kB
1
Indexable
Never
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll Mod = 1e9 + 7;
const int N = 1e3;
int p[N + 2];
vector<int>pr;
const int M = 170;
bitset<M>b[M + 2];
int sz = 0;
void insrt(bitset<M>x){
    for(int i=0;i<M;i++){
        if(!x[i])
            continue;
        if(!b[i].any()){
            b[i] = x;
            sz++;
            return;
        }
        x ^= b[i];
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    for(int i=2;i<=N;i++){
        if(!p[i]){
            pr.push_back(i);
            for(int j=2*i;j<=N;j+=i){
                p[j] = 1;
            }
        }
    }
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        bitset<M>y;
        for(int i=0;i<pr.size();i++){
            int r = pr[i];
            if(x % r == 0){
                while(x % r == 0){
                    x /= r;
                    y[i] = !(y[i]);
                }
            }
        }
        insrt(y);
    }
    n -= sz;
    ll ans = 1;
    for(int i=0;i<n;i++){
        ans = ans * 2 % Mod;
    }
    ans = ans + Mod - 1;
    ans %= Mod;
    cout<<ans;
}
Leave a Comment