记录编号	577961	评测结果	AAAAAAAAAA
题目名称	[UVa 11542] 乘积是平方数	最终得分	100
用户昵称	op_组撒头屯	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2022-12-16 10:31:47	内存使用	0.00 MiB

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100+5;
const int M=95+5;
ll p[]={0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499}; 
int n,m=95;
int a[M][N];
int main(){
	freopen ("square1.in","r",stdin);
	freopen ("square1.out","w",stdout);
	int T;scanf("%d",&T);
	while(T--){
		scanf("%d",&n);
		memset(a,0,sizeof(a));
		for (int i=1;i<=n;i++){
			ll x;scanf("%lld",&x);
			for (int j=1;j<=m;j++){
				if (x%p[j]==0){
					int cnt=0;
					while(x%p[j]==0){
						x/=p[j];cnt^=1;
					}
					a[j][i]=cnt;
				}
			}
		}
		int r,c;
		for (r=1,c=1;r<=m&&c<=n;r++,c++){
			int pos=0;
			for (int j=r;j<=m;j++){
				if (a[j][c]){
					pos=j;break;
				}
			}
			if (!pos){
				r--;continue;
			}
			swap(a[r],a[pos]);
			for (int j=1;j<=m;j++){
				if (j==r||!a[j][c])continue;
				for (int k=c;k<=n;k++)a[j][k]^=a[r][k];
			}
		}
		printf("%lld\n",(1ll<<(n-r+1))-1);
	}
	return 0;
}