记录编号	578175	评测结果	AAAAAAAAAA
题目名称	[UVa 11542] 乘积是平方数	最终得分	100
用户昵称	HeSn	是否通过	通过
代码语言	C++	运行时间	0.233 s
提交时间	2023-02-07 22:09:00	内存使用	5.77 MiB

#include<bits/stdc++.h>
using namespace std;
#define int unsigned long long
bitset<510> b[510];
int n, p[510], vis[510], num;
void prime() {
	for(int i = 2; i <= 500; i ++) {
		if(!vis[i]) {
			p[++ num] = i;
		}
		for(int j = 1; p[num] * j <= 500; j ++) {
			vis[p[i] * j] = 1;
		}
	}
}
signed main() {
	freopen("square1.in", "r", stdin);
	freopen("square1.out", "w", stdout);
	prime();
	int t;
	cin >> t;
	for(int tt = 1; tt <= t; tt ++) {
		cin >> n;
		memset(b, 0, sizeof(b));
		int maxn = 0;
		for(int i = 1; i <= n; i ++) {
			int x;
			cin >> x;
			for(int j = 1; p[j] <= x && j <= num; j ++) {
				int k = p[j];
				if(x % k == 0) {
					maxn = max(maxn, j);
					int w = 0;
					while(x % k == 0) {
						w ^= 1;
						x /= k;
					}
					b[j][i] = w;
				}
			}
		}
		int pos = 1, sum = 0;
		for(int i = 1; i <= n; i ++) {
			int flg = 1;
			for(int j = pos; j <= maxn; j ++) {
				if(b[j][i]) {
					if(pos != j) {
						swap(b[j], b[pos]);
					}
					for(int k = 1; k <= maxn; k ++) {
						if(k == pos) {
							continue;
						}
						if(b[k][i]) {
							b[k] ^= b[pos];
						}
					}
					flg = 0;
					pos ++;
					break;
				}
			}
			if(flg) {
				sum ++;
			}
		}
		int ans = 1;
		for(int i = 1; i <= sum; i ++) {
			ans *= 2;
		}
		cout << ans - 1 << endl;
	}
	return 0;
}