【题意】给出n个整数，从中选出1个或者多个，使得选出的整数乘积是完全平方数。一共有多少种选法？
【解题方法】高斯消元，不得不吐槽这场网络赛，这道题是白书的原题，可惜没有发现，最后队友们还是做出来的。参考白书p160
【AC 代码】
#include <cstdio> #include <cmath> #include <cstring> #include <iostream> #include <algorithm> using namespace std; typedef long long LL; const int maxn = 510; const int maxp = 2010; const LL mod=1e9+7; int prime[maxp],vis[2010]; void seive(int n) { int m=(int)sqrt(n+0.5); memset(vis,0,sizeof(vis)); for(int i=2; i<=m; i++) if(!vis[i]) for(int j=i*i; j<=n; j+=i) vis[j]=1; } int getprime(int n) { seive(n); int c=0; for(int i=2; i<=n; i++){ if(!vis[i]) prime[c++]=i; } return c; } LL powmod(LL a,LL n) { LL res=1; while(n){ if(n&1) res=res*a%mod; a=a*a%mod; n>>=1; } return res; } int A[maxn][maxn];//系数矩阵 int solve(int m,int n) { int i=0,j=0,k,r,u; while(i<m&&j<n){ r=i; for(k=i; k<m; k++) if(A[k][j]){r=k; break;} if(A[r][j]){ if(r!=i) for(k=0; k<=n; k++) swap(A[r][k],A[i][k]); for(u=i+1; u<m; u++) if(A[u][j]) for(k=i; k<=n; k++) A[u][k]^=A[i][k]; i++; } j++; } return i; } int main() { int m=getprime(2010); int T,cas=1; cin>>T; while(T--){ int n,maxp=0; LL x; scanf("%d",&n); memset(A,0,sizeof(A)); for(int i=0; i<n; i++){ scanf("%lld",&x); for(int j=0; j<m; j++){ while(x%prime[j]==0){maxp=max(maxp,j);x/=prime[j];A[j][i]^=1;} } } LL r=solve(maxp+1,n); LL tmp=n-r; LL ans=powmod(2,tmp)-1; printf("Case #%d:\n",cas++); printf("%lld\n",ans); } return 0; }