线性基应用（CF895C Square Subsets）

本题考虑的是平方数的性质，即平方数的每个质因数的出现次数为偶数，那么对于n个数而言，它们的质因数次数为偶数的标记为0，奇数的标记为1，那么由线性基的性质可得最少的基底数，可以表示所有的线性空间。所以除开基地，即可以选择任意的数字，所以答案即是

#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7,N = 1e5 + 10;
int n;
int p[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67};
int d[40];
int a[N];
void insert(int x){
    for(int i=18;i>=0;i--){
        if(!(x >> i)) continue;
        if(!d[i]){
            d[i] = x;
            break;
        }
        x ^= d[i];
    }
}
int qmi(int a,int b){
    int res=1;
    while(b){
        if(b&1)    res=1LL*res*a%mod;    a=1LL*a*a%mod;    b>>=1;
    }
    return res;
}
int main(){
    cin >> n;
    for(int i=1;i<=n;i++){
        int x;
        cin >> x;
        for(int j=0;j<=18;j++){
            if(x % p[j] == 0){
                int num = 0;
                while(x % p[j] == 0) x /= p[j],num ^= 1;
                a[i] |= num << j;
            }
        }
    }
    for(int i=1;i<=n;i++) insert(a[i]);
    for(int i=0;i<=18;i++) if(d[i]) n--;
    cout <<qmi(2,n) - 1 << endl;
    return 0;
}