本题考虑的是平方数的性质,即平方数的每个质因数的出现次数为偶数,那么对于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; }