题目链接：UVA11542 Square

题目大意：

有 T 组数据，每组数据中有 n 个数，分别为 a_{1},a_{2},a_{3}…a_{n}。从这 n 个数中任选一个或多个数使得所取出来的数的乘积为完全平方数，问有多少种取法。
其中 1 \leq T\leq 30,1 \leq N\leq 100,1 \leq a_{i}\leq 10^{15}，并且每个数不包含大于 500 的质因子。

解题思路：

可以将集合里的每个数拆成素数之积，比如第三组，4 = 2^2 ，6 = 2^1 * 3^1 ， 10 = 2^1 * 5^1 ， 15 = 3^1 * 5^1。
能拆出来的素数因子有三个，就列三个方程，将 4,6,10,15 这四个数记做 X_1，X_2，X_3，X_4。他们取 1 代表要选这个数字，取 0 等于不选这个数字。

对于素数因子 2 ： 2X_1 + 1X_2 + 1X_3 + 0X_4 = 0
对于素数因子 3 ： 0X_1 + 1X_2 + 0X_3 + 1X_4 = 0
对于素数因子 5 ： 0X_1 + 0X_2 + 1X_3 + 1X_4 = 0

由于要使得最终的积可以开根，所以每个因子的指数得是偶数。
所以可以把系数模2得到：

对于素数因子 2 ： 0X_1 + 1X_2 + 1X_3 + 0X_4 = 0
对于素数因子 3 ： 0X_1 + 1X_2 + 0X_3 + 1X_4 = 0
对于素数因子 5 ： 0X_1 + 0X_2 + 1X_3 + 1X_4 = 0

系数矩阵：

\begin{matrix}
0 &1 &1 &0\cr
0 &1 &0 &1\cr
0 &0 &1 &1\cr
\end{matrix}

然后将它异或消元，可以得到系数矩阵的秩 x，则一共有 n-x+1 个自由变元。刨除全不选，答案为 2^{n-x+1}-1。

AC代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 105;
const int M = 505;
bitset<N> a[N];
long long b[N];
int maxp;

int prime[M], num[M], tot;
void pre() {
    for (int i = 2; i < M; i++) {
        if (!num[i]) {
            prime[++tot] = i;
        }
        for (int j = 1; j <= tot && i * prime[j] < M; j++) {
            num[i *prime[j]] = 1;
            if (i % prime[j] == 0) break;
        }
    }
}

void init(int n) {
    maxp = 0;
    for (int i = 1; i <= tot; i++) {
        a[i].reset();
    } 
    for (int i = 1; i <= n; i++) {
        long long x = b[i];
        for (int j = 1; prime[j] <= x && j <= tot; j++) {
            if (x % prime[j] == 0) {
                int cnt = 0;
                while (x % prime[j] == 0) {
                    cnt ^= 1; x /= prime[j];
                }
                a[j][i] = cnt;
                maxp = max(maxp, j);
            }
        }
    }
}

int Gauss(int n, int m) {
    int i = 1, j = 1, r;
    while (i <= n && j <= m) {
        r = i;
        for (int k = i; k <= n; k++) {
            if (a[k][j]) {
                r = k; break;
            }
        }
        if (a[r][j]) {
            if (r != i) swap(a[i], a[r]);
            for (int k = 1; k <= n; k++) {
                if (k != i && a[k][j]) a[k] ^= a[i];
            }
            i++;
        }
        j++;
    }
    return i;
}

int main() {
    pre();
    int T, n; scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            scanf("%lld", &b[i]);
        }
        init(n);
        int ans = n - Gauss(maxp, n) + 1;
        printf("%lld\n", (1LL << ans) - 1);
    }
    return 0;
}