从数组中选择几个数，要求他们的乘积可以开平方，问有多少种方案。
先将单个数拆分成质因子，对于这个数而言，那些指数为奇数的质因子会使这个数无法被开平方。
所以我们需要选择一个对应质因子指数为奇数的元素，将他们两个放在一个方案中，但是又有可能会引入其他的质因子。
这样就变成了求解行列式中*变元的数量问题。
将数组转换成行列式，利用高斯消元求解。
代码如下：
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std; bool pri[];
int a[][];
int max_;
int t, n;
long long x;
vector<int>V; void Prime(){
memset(pri,,sizeof(pri));
pri[] = pri[] = ;
for(int i=;i<;i++)if(pri[i]){
V.push_back(i);//对素数离散一下 优化一下
for(int j=i<<;j<;j+=i)
pri[i] = ;
}
}
void init(){
memset(a,,sizeof(a));
max_ = ;
}
int gauss(){// 高斯消元
int i = , j = ;
while(i<=max_ && j<n){
int k = i;
for(;k<=max_;k++)
if(a[k][j])break;
if(k != max_ + ){
for(int l=;l<n;l++){
// 第j个等式的 k位上为 1
// 将第 k 行与第 i 行 进行 行交换
swap(a[i][l],a[k][l]);
}
for(int k=i+;k<=max_;k++){
if(a[k][j]){
for(int l=j;l<n;l++)
a[k][l] ^= a[i][l];// 这里是优化后的式子
}
}
i++;
}
j++;
}
return n-i;
}
int main(){
Prime();
scanf("%d",&t);
while(t--){
init();
scanf("%d",&n);
for(int i=;i<n;i++){
scanf("%lld",&x);
for(int j=;j<V.size() && V[j]<= x;j++){
while(x%V[j] == ){
a[j][i] ^= ;
// 若 质因子的指数为偶数 则行列式对应位上为 0
// 奇数 为 1
max_ = max(max_, j);
// 记录一下最大值， 优化
x /= V[j];
}
}
}
printf("%lld\n",(1ll<<gauss())-);
}
return ;
}