链接：http://acm.hdu.edu.cn/showproblem.php?pid=5833
题意：
给出n个数，每次可以从中取任何数，问有多少种取法使得取出来的数的乘积是完全平方数。
题解：
首先显然可以去掉偶数幂的质因子，每个数就变成了不同质数相乘的形式，已知题意中只有大约300多个质因子，直接列成质因子的01矩阵形式，高斯消元，求一下自由变元个数temp，显然答案就是temp^1-1。
CODE：
#include <bits/stdc++.h> using namespace std; #define INF 0x3f3f3f3f #define bug cout<<"bug\n" const int maxn = 1e5+7; #define MAXN 2030 const long long mod = 1e9+7; bool not_prime[MAXN*30]; long long prime[MAXN]; int num_prime; int a[350][350]; void get_prime() { long long i,j; memset(not_prime,0,sizeof(not_prime)); num_prime=0; not_prime[1]=1; for(i=2; i<MAXN; ++i) if(!not_prime[i]) { num_prime++; prime[num_prime]=i; for(j=i*i; j<MAXN; j+=i) not_prime[j]=1; } } int gauss(int m, int n) { int i,j,k,r; for(i=j=0; i<m&&j<n ; ++i,++j) { r=i; for(int c=i; c<m; ++c) if(a[c][j]){r=c;break;} if(a[r][j]) { if(r!=i)for(int c=0; c<=n; ++c)swap(a[r][c],a[i][c]); for(k=i+1; k<m; ++k)if(a[k][j]) for(int c=i; c<=n; ++c) a[k][c]^=a[i][c]; } else --i; } return i; } int main() { int T; int n,m; long long p; scanf("%d",&T); int cas=1; get_prime(); while(T--) { memset(a,0,sizeof(a)); scanf("%d",&n); int M=0; for(int i=0; i<n; ++i) { scanf("%I64d",&p); for(int j=1; p>=prime[j] && j<=num_prime; ++j) { while(p%prime[j]==0) { M=max(M,j); p/=prime[j]; ++a[i][j-1]; } a[i][j-1]%=2; } } long long temp=n-gauss(n,M); long long ans=1; for(int i=0; i<temp; ++i){ans<<=1LL;ans%=mod;} printf("Case #%d:\n%I64d\n",cas++,ans-1); } return 0; } /* 100 3 3 3 4 3 2 2 2 5 4 4 4 4 4 9 4 4 4 4 4 5 5 5 5 6 4 4 80 20 5 5 */