题意：给定n个数，这n个数的素因子值不超过2000，从中取任意个数使其乘积为完全平方数，问有多少种取法。
题解：开始用素筛枚举写了半天TLE了，后来队友说高斯消元才想起来，果断用模板。赛后又得知这是个原题sgu200，真坑啊。把每个数进行素因子分解，素因子a的幂为奇数则视为1，偶数则视为0，转化为从n个数中取数异或和为0有多少种取法的问题。
AC代码：
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
#define maxn 305
using namespace std;
typedef long long ll;
ll T, N;
ll beg[maxn], end[maxn], x[maxn];
ll a[maxn][maxn]; ll Gauss_XOR(ll a[maxn][maxn], ll x[maxn], ll var, ll equ)
{
ll row, col;
for (row = col = ; row <= equ && col <= var; ++row, ++col)
{
if (!a[row][col])
{
for (int i = equ; i > row; --i)
{
if (a[i][col])
{
for (int j = row; j <= var + ; ++j)
{
swap(a[i][j], a[row][j]);
}
break;
}
}
}
if (!a[row][col])
{
--row;
continue;
}
for (int i = row + ; i <= equ; ++i)
{
if (a[i][col])
{
for (int j = var + ; j >= col; --j)
{
a[i][j] ^= a[row][j];
}
}
}
}
for (int i = row; i <= equ; ++i)
{
if (a[i][var + ]) return -;
}
if (row <= var)
{
return var - row + ;
}
for (int i = var; i >= ; --i)
{
x[i] = a[i][var + ];
for (int j = i + ; j <= var; ++j)
{
x[i] ^= a[i][j] && x[j];
}
}
return ;
}
const long long mod=;
ll prime[],cnt=;
ll isprime[];
ll data[][];
void get()
{
for(int i=; i<=; i++)
isprime[i]=;
for(int i=; i<=; i++)
{
if(isprime[i]==)
{
prime[cnt++]=i;
for(int j=i+i; j<=; j+=i)
isprime[j]=;
}
}
}
int main()
{
ll num;
int cas=;
get();
scanf("%lld", &T);
while (T--)
{
ll equ = ;
memset(x, , sizeof (x));
memset(a, , sizeof (a));
scanf("%lld", &N);
for(int i = ; i <= N; ++i)
{
memset(data,,sizeof(data));
ll pos = ;
scanf("%lld", &num);
ll tmp1=num,tmp2=;
for(int j=; j<cnt; j++)
{
int sum=;
if(tmp1%prime[j]==)
{
tmp1/=prime[j];
sum++;
while(tmp1%prime[j]==)
{
tmp1/=prime[j];
sum++;
}
}
if(sum%==)
data[j/][j%]=;
}
int b=;
int ii=,jj=;
while(b--)
{
if(jj==)
{
ii++;
jj=;
}
if(data[ii][jj++] & ) a[pos][i] = ;
else a[pos][i] = ;
//num >>= 1;
++pos;
}
equ = max(equ, pos - );
}
for(int i = ; i <= ; ++i)
a[i][N + ] = ;
ll ans = Gauss_XOR(a, x, N, equ);
if (ans == -) puts("-1");
else
{
ll prt = ;
for(int i = ; i <= ans; ++i)
{
prt <<= ;
prt %= mod;
}
printf("Case #%d:\n",cas++);
prt=(prt-+mod)%mod;
printf("%lld\n", prt);
}
}
return ;
}
之前写的TLE素筛：
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
const long long mod=;
ll prime[],cnt=;
ll isprime[],isprime2[];
ll data[][];
void get()
{
for(int i=; i<=; i++)
isprime[i]=;
for(int i=; i<=; i++)
{
if(isprime[i]==)
{
prime[cnt++]=i;
for(int j=i+i; j<=; j+=i)
isprime[j]=;
}
}
}
int main()
{
get();
//
int num[cnt+];
int t,cas=,a[];
/* ll c=1;
for(int i=0;i<15;i++)
c*=prime[i];
printf("%lld\n",b);*/
scanf("%d",&t);
while(t--)
{
int n;
memset(a,,sizeof(a));
memset(data,,sizeof(data));
scanf("%d",&n);
for(int i=; i<n; i++)
scanf("%d",&a[i]);
sort(a,a+n);
ll sum=,k=-,flag1=;
ll tmp1;
for(int i=; i<; i++)
{
sum=;
k=-;
flag1=;
for(int j=; j<n; j++)
{
tmp1=a[j];
if(tmp1==-) continue;
if(tmp1%prime[i]==)
{
//cout<<tmp1<<" *** "<<prime[i]<<endl;
tmp1/=prime[i];
sum++;
flag1++;
while(tmp1%prime[i]==)
{
tmp1/=prime[i];
sum++;
}
k=j;
}
if(flag1>=)
break;
}
//cout<<prime[i]<<" "<<sum<<" "<<flag1<<endl;
if(flag1==&&((sum%)==))
a[k]=-;
}
for(int i=; i<n; i++)
{
if(a[i]==-)
{
for(int j=i; j<n; j++)
{
a[j]=a[j+];
}
i--;
n--;
}
}
ll tmp=;
memset(num,,sizeof(num));
ll tmp2;
for(int i=;i<n;i++)
{
tmp=;
for(int j=;j<cnt;j++)
{
tmp2=a[i];
if(!tmp2) break;
if(tmp2%prime[j]==&&tmp2!=)
{
tmp2/=prime[j];
data[i][prime[j]]++;
while(tmp2%prime[j]==)
{
tmp2/=prime[j];
data[i][prime[j]]++;
}
data[i][prime[j]]%=;
}
}
}
// cout<<data[0][3]<<endl;
// cout<<data[1][3]<<endl;
// cout<<data[2][2]<<endl;
// for(int i=0;i<n;i++)
// {
// cout<<a[i]<<" ";
// }cout<<endl;
ll pre[];
ll ans=-;
for(int i=;i<(<<n);i++)
{
memset(pre,,sizeof(pre));
for(int j=;j<n;j++)
{
if(i&(<<j))
{
for(int x=;x<=;x++)
{
pre[x]+=data[j][x];
pre[x]%=;
}
}
}
int flag=;
for(int k=;k<cnt;k++)
{
if(pre[prime[k]]%==)
{
flag=;
break;
}
}
if(flag==)
{
//cout<<i<<"***"<<endl;
ans++;
ans%=mod;
}
}
printf("Case #%d:\n",cas++);
printf("%lld\n",ans);
}
return ;
}