Uva 11542 Square
题目中说数组中的数的最大质因子不超过500，我们筛出≤500的质数，然后考虑对每个质数列一个方程组。。
然后这几乎就是高斯消元求解异或方程组的模板题了。。。。
注意答案是 2^(*元数量)-1，因为空集不是答案的一部分。。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
#define ll long long
#define maxn 125
using namespace std;
int zs[505],t=0;
bool v[505];
inline void init(){
for(int i=2;i<=500;i++){
if(!v[i]) zs[++t]=i;
for(int j=1,u;j<=t&&(u=zs[j]*i)<=500;j++){
v[u]=1;
if(!(i%zs[j])) break;
}
}
}
int a[maxn][maxn];
int T,n,m;
ll now;
inline void prework(int x){
for(int i=1;i<=t;i++) if(!(now%zs[i])){
int c=0;
while(!(now%zs[i])) now/=(ll)zs[i],c^=1;
a[i][x]=c;
}
}
inline int solve(){
int i=1,j=1;
//当前处理到第i个方程，第j个变量
while(i<=t&&j<=n){
for(int k=i;k<=t;k++) if(a[k][j]){
if(k!=i) for(int l=j;l<=n;l++) swap(a[k][l],a[i][l]);
break;
}
if(a[i][j]){
for(int k=i+1;k<=t;k++) if(a[k][j])
for(int l=j;l<=n;l++) a[k][l]^=a[i][l];
i++;
}
j++;
}
return i-1;
}
int main(){
init();
scanf("%d",&T);
while(T--){
memset(a,0,sizeof(a));
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%lld",&now);
prework(i);
}
int d=solve();
printf("%lld
",((ll)1<<(ll)(n-d))-1ll);
}
return 0;
}