题意：给n个数，从n个数中抽取x(x>=1)个数，这x个数相乘为完全平方数，求一共有多少种取法，结果模1000000007。
思路：每个数可以拆成素数相乘的形式，例如:
x1 2=2^1 * 3^0 * 5^0;
x2 3=2^0 * 3^1 * 5^0;
x3 4=2^2 * 3^0 * 5^0;
x4 5=2^0 * 3^0 * 5^1;
x5 6=2^1 * 3^1 * 5^0;
x6 15=2^0 * 3^1 * 5^1;
用xi表示第i个数选或不选，xi的取值为0或1；因为相乘结果为完全平方数，所以最后的完全平方数表示成素数相乘的形式后，每个素数的幂一定是偶数，即模2等于0:
2 (x1+2*x3+x5)%2=0
3 (x2+x5+x6)%2=0
5 (x4+x6)%2=0
将上面的式子转化为异或方程组，求解有m个*变量，每个*变量都可以取0或1，最终答案为2^m-1（去掉全0的情况）;
#include <bits/stdc++.h>
using namespace std;
#define MAXN 2000
int prime[MAXN+];
int a[MAXN+][];
int free_num;
int free_x[MAXN];
int x[];
int equ,var;
const int mod=;
void getprime()
{
int i,j;
memset(prime,,sizeof(prime));
prime[]=prime[]=;
for(i=;i<=MAXN;i++)
{
if(prime[i])
prime[++prime[]]=i;
for(j=;j<=prime[]&&i*prime[j]<=MAXN;j++)
{
prime[i*prime[j]]=;
if(i%prime[j]==)
break;
}
}
}
void geta(int id,long long num)
{
int i;
i=;
while(num!=)
{
while(num%prime[i]==)
{
num/=prime[i];
a[i-][id]^=;
}
i++;
}
}
//返回值为-1表示无解，为0是唯一解，否则返回*变元个数
int Gauss()
{
int max_r, col, k;
free_num = ;
for(k = , col = ; k < equ && col < var; k++, col++)
{
max_r = k;
for(int i = k ; i < equ; i++)
if(abs(a[i][col]==)
{
max_r = i;
break;
}
if(a[max_r][col] == )
{
k--;
free_x[free_num++] = col; //*变元
continue;
}
if(max_r != k)
{
for(int j = col; j < var+; j++)
swap(a[k][j],a[max_r][j]);
}
for(int i = k+; i < equ;i++)
if(a[i][col] != )
for(int j = col; j < var+;j++)
a[i][j] ^= a[k][j];
}
for(int i = k;i < equ;i++)
if(a[i][col] != )
return -;
if(k < var)return var-k;
return ;
}
int main()
{
int ans;
int t;
int n;
int i;
int cas;
int freex;
long long num;
scanf("%d",&t);
getprime();
//printf("%d\n",prime[0]);
for(cas=;cas<=t;cas++)
{
memset(a,,sizeof(a));
scanf("%d",&n);
for(i=;i<n;i++)
{
scanf("%I64d",&num);
geta(i,num);
}
equ=prime[];
var=n;
freex=Gauss();
//printf("::%d\n",freex);
if(freex==-)
ans=;
else if(freex==)
ans=;
else
{
ans=;
for(i=;i<freex;i++)
{
ans=(*ans)%mod;
}
ans--;
}
printf("Case #%d:\n%d\n",cas,ans);
}
return ;
}