题目大意：给出n个数字a[]，将a[]分解为质因子（保证分解所得的质因子不大于2000）,任选一个或多个质因子，使其乘积为完全平方数。求其方法数。
学长学姐们比赛时做的，当时我一脸懵逼的不会搞……所以第二天上午花了一上午学习了一下线性代数。
题目思路：
任选一个或多个质因子，起乘积为完全数m，因为组成它的均为素数，假设组成m的素数的种类为n，那么这n类素数中每类素数的个数应为偶数。
可设：a[i][j]=0代表第i种素数可在a[j]中分离出的个数为偶数，a[i][j]=1代表第i种素数可在a[j]中分离出的个数为奇数数。
b[i]=1代表选择这类素数，b[i]=0代表不选择这类素数。
列出线性方程组：
a11x1+a12x2+...+a1nxn=0
a21x1+a22x2+...+a2nxn=0
...
an1x1+an2x2+...+annxn=0
求解的个数 ans
转化为矩阵形式：
矩阵A=
a11 a12 a13 …………a1n
a21 a22 a23 …………a2n
……………………………………
……………………………………
an1 an2 an3 …………ann
通过初等变换可将矩阵A换成类似下面矩阵B的形式
a11 a12 a13 ……a1n
0 a22 a23 ……a2n
0 0 a33……a3n
0 0 0 ……arn
再将矩阵B转化成线性方程组 可求出最后一组方程的解，倒着往回求可求出所有方程解
可解出的方程组共 r 个，由秩的定义可知 r等矩阵A的秩
由定理：
对于n元齐次线性方程组如果r<n，则方程组含n-r个*未知量。
解的个数ans=2^（n-r）-1(减去全0解)
具体操作：
#include<cstdio>
#include<stdio.h>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#define INF 0x3f3f3f
#define MAX 2105
#define MOD 1000000007 using namespace std; long long c[MAX][],p[MAX],v[MAX],a[MAX],cnt,n;//c存矩阵，p存素数表，cnt代表素数的个数 void MakeTab()//打素数表
{
int i,j;
memset(v,,sizeof(v));
memset(p,,sizeof(p));
cnt=;
for(i=; i<=; i++)
{
if(!v[i])
{
p[++cnt]=i;
for(j=i; j<=; j+=i)
{
v[j]=;
}
}
}
} int Rank()//计算秩
{
int i,j,k,r,u;
i=;
j=;
while(i<=cnt && j<=n)
{
r=i;
while(!c[r][j] && r<=cnt)
r++;
if(c[r][j])
{
swap(c[i],c[r]);//如果发现了第r行第j列为1，就讲r行和i行行互换（初等行变换）
for(u=i+; u<=cnt; u++)
{
if(c[u][j])
{
for(k=i; k<=n; k++)
{
c[u][k]=c[u][k]^c[i][k];//每找到一个未知数就对其进行亦或处理，去掉系数c[i][k]
} }
}
i++;
}
j++;
}
return i;
} int main()
{
MakeTab();
int i,j,cns=,T;
scanf("%d",&T);
while(T--)
{
scanf("%lld",&n);
memset(c,,sizeof(c));
for(i=; i<=n; i++)
{
scanf("%lld",&a[i]);
} for(i=; i<=n; i++)
{
for(j=; j<=cnt; j++)
{
long long num=a[i];
if(num%p[j]==)
{
while(num%p[j]==)
{
num/=p[j];
c[j][i]=c[j][i]^;
}
}
}
} long long k=(n-Rank());
long long ans=;
for(i=; i<=k; i++)
ans=(ans*)%MOD;
printf("Case #%d:\n",cns++);
printf("%lld\n",ans-);//去掉全0的解
}
return ;
}