记录编号	86113	评测结果	AAAAAAAAAA
题目名称	[UVa 11542] 乘积是平方数	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.112 s
提交时间	2014-01-20 21:06:01	内存使用	2.30 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#include<iomanip>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
const int SIZEP=510,SIZEN=510;
vector<int> prime;
void getprime(int n){
	bool flag[SIZEP]={0};
	for(int i=2;i<=n;i++){
		if(!flag[i]){
			prime.push_back(i);
			for(int j=i*i;j<=n;j+=i) flag[j]=true;
		}
	}
}
int xor_rank(ll A[SIZEN][SIZEN],int b[SIZEN],int n,int m){
	//使用高斯约当消元法,求异或方程组的秩
	//A是异或方程组,b是方程右边的常数向量,n是行数,m是列数
	int i,j,k;
	for(i=1;i<=n;i++){//第i次消元
		for(k=i;k<=m;k++){//选取消元列
			for(j=i;j<=n;j++){//选取消元行
				if(A[j][k]) goto BREAK;
			}
		}
		BREAK:;
		if(j==n+1) break;//找不到可消元的元素了
		if(i!=j){//交换行
			for(int km=1;km<=m;km++) swap(A[i][km],A[j][km]);
			swap(b[i],b[j]);
		}
		if(i!=k) for(int km=1;km<=n;km++) swap(A[km][i],A[km][k]);//交换列
		for(j=1;j<=n;j++){//消元
			if(j==i) continue;
			if(A[j][i]){
				for(int km=1;km<=m;km++) A[j][km]^=A[i][km];
				b[j]^=b[i];
			}
		}
	}
	return i-1;
}
int N,M;
ll A[SIZEN][SIZEN]={0};
int b[SIZEN]={0};
void work(void){
	scanf("%d",&N);
	memset(A,0,sizeof(A));
	memset(b,0,sizeof(b));
	int i,j;
	ll x;
	for(i=1;i<=N;i++){
		scanf("%lld",&x);
		j=0;
		while(x>1&&j<M){
			while(x%prime[j]==0){
				A[j+1][i]^=1;
				x/=prime[j];
			}
			j++;
		}
	}
	ll ans=xor_rank(A,b,M,N);
	ans=N-ans;
	cout<<(1LL <<ans)-1<<endl;//这里的LL很重要
}
int main(){
	freopen("square1.in","r",stdin);
	freopen("square1.out","w",stdout);
	getprime(500);
	M=prime.size();
	int T;
	scanf("%d",&T);
	while(T--) work();
	return 0;
}