时间限制：0.25s
空间限制：4M
题意：
给出了m（<100）个数，这m个数的质因子都是前t(<100)个质数构成的。
问有多少个这m个数的子集，使得他们的乘积是完全平方数。
Solution：
要使乘积为完全平方数，那么对于乘积的每个质因子的个数要为偶数。
可以先打出前100个质数，来看第i个质数Pi，对于第j个数Kj，如果它含有奇数个质数Pi，那么矩阵A[i][j]的值为1,显然增广矩阵的值应该全为0.
这样就构造出了一个n*m的xor方程组.
利用高斯消元求出变元的个数power
那么答案就是(2^power)-1
wa了几次竟然是因为高精度写错了,真是醉了...
code
/*
解异或方程组
*/
#include <iostream>
#include <vector>
using namespace std;
const int MAXN = ; int prim[MAXN];
vector<int> A[MAXN]; int Gauss (int n, int m) {
int col = , row = , tem, k = ;
for (; col <= m && row <= n; ++col) {
for (tem = ++row; tem <= n && A[tem][col] == ; ++tem);
if (tem > n) {
row--;
continue;
}
if (tem != row) swap (A[tem], A[row]);
for (int i = row + ; i <= n; ++i) {
if (A[i][col])
for (int j = col; j <= m; ++j)
A[i][j] ^= A[row][j];
}
}
return m - row;
}
void init() {
bool vis[] = {};
for (int i = , tol = ; i <= ; ++i)
if (!vis[i]) {
prim[++tol] = i;
for (int j = i; j <= ; j += i)
vis[j] = ;
}
}
int n, m;
void output (int x) {
if (x <= ) {
cout << << endl;
return;
}
int C[] = {}, len = ;
for (int i = ; i <= x; ++i) {
for (int j = ; j <= len; ++j)
C[j] <<= ;
C[]++;
for (int t = ; t <= len ; t++)
if (C[t] >= ) {
C[t + ] += C[t] / ;
C[t] %= ;
if (t + > len) len++;
}
}
for (int i = len; i > ; --i)
cout << C[i];
} int main() {
ios::sync_with_stdio ();
init();
cin >> n >> m;
for (int i = ; i < MAXN; i++) A[i].resize (MAXN);
for (int i = , x; i <= m; ++i) {
cin >> x;
for (int j = ; j <= n; ++j)
for (; x % prim[j] == ; x /= prim[j]) A[j][i] ^= ;
}
int power = Gauss (n, m);
output (power);
}