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\n",((ll)1<<(ll)(n-d))-1ll);

	}

	return 0;

}