题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5833
题意：给n个数，选择一些数字乘积为平方数的选择方案数。
分析：每一个数字分解质因数。比如4， 6， 10， 15，,
,
,
, 令
，
表示选择第i个数字，那么
，如果p是平方数，那么每个质因数上的指数为偶数，x1系数为2已经是偶数不考虑。可以转换为异或为0判断偶数，即奇数置为1，偶数置为0，然后n个数字m个质因数的增广矩阵消元看有几个*变量(取0或1无所谓)，答案是2^r - 1(全部都不取方案不算)
线性方程组的*变量个数了（即方程个数 - 增广矩阵的秩）。
比如：n=2个数 8 =2^3 、 9 = 3^2
有两个素因子2和3，可列出两个方程：
3*X1 + 0*X2 = 0 (mod2) 等价于 ： X1 +0*X2 = 0
0*X1 + 2*X2 = 0 (mod2) 0*X1 + 0*X2 = 0
其中只有1个有效方程，即秩为1。
这代表什么意思呢？ X1 = 0 , 表示8一定不能选 ， X2不确定，表示9可以选择也可以不选。
因此答案为 2^1 - 1 = 1 （因为不允许一个都不选，所以减一）
网选原题的并不只这一题，没做过的只能默默吃亏了；
相对应的UVA的11542：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2537同时也是大白书上的例题；
#include<iostream>
#include<algorithm>
#include<string.h>
#include<stdio.h>
using namespace std;
#define N 2000
#define met(a, b) memset(a, b, sizeof(a))
#define mod 1000000007
typedef long long LL; int f[N*], p[N*], Matrix[N][N]; int Prime()
{
int cnt = ;
for(int i=; i<N; i++)
{
if(!p[i])f[cnt++] = i;
for(int j=i; j<N; j+=i)
p[j] = ;
}
return cnt;
} int gauss(int m, int n)
{
int i = , j = ;
while(i<m && j<n)
{
int row = i;
for(int k=i+; k<m; k++)
{
if(Matrix[k][j])
{
row = k;
break;
}
}
if(Matrix[row][j])
{
if(row != i)
{
for(int k=; k<=n; k++)
swap(Matrix[i][k], Matrix[row][k]);
}
for(int p=i+; p<m; p++)
{
if(Matrix[p][j])
{
for(int q=i; q<=n; q++)
Matrix[p][q] ^= Matrix[i][q];
}
}
i++;
}
j++;
}
return i;
} int main()
{
int PrimeNum = Prime(); int n, T, t = ; scanf("%d", &T);
while(T--)
{
met(Matrix, );
scanf("%d", &n);
int m = ;
for(int i=; i<n; i++)
{
LL num;
scanf("%I64d", &num);
for(int j=; j<PrimeNum; j++)
{
if(num%f[j] == )
{
m = max(m, j);
while(num%f[j] == )
{
num/=f[j];
Matrix[j][i] ^= ;
}
}
}
}
int ret = gauss(m+, n); LL ans = ;
for(int i=; i<=n-ret; i++)
{
ans = ans*%mod;
}
ans = (ans+mod-) % mod;
printf("Case #%d:\n%I64d\n", t++, ans);
}
return ;
}