题解：2000以内的质因数为303个。
以质因数为方程个数，a[i]的取或不取为未知数，解xor的高斯方程
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <cmath> using namespace std; typedef long long LL; const int M=1000000007; const int N=300+10; int h,p[2002]; int n; int RP(int a,int b) { int Ans=1; for (;b;b>>=1){ if (b&1)Ans=1LL*Ans*a%M; a=1LL*a*a%M; } return Ans; } void prime() { memset(p,0,sizeof p); h=0; for (int i=2;i<=2000;i++)if (!p[i]){ p[h]=i;h++; for (int j=i;j<=2000;j+=i)p[j]=1; } } typedef int Matrix[N][N]; int Rank(Matrix A,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; } Matrix A; int main() { prime();//printf("%d\n",h); int Case;scanf("%d",&Case); for (int C=1;C<=Case;C++){ printf("Case #%d:\n",C); scanf("%d",&n); memset(A,0,sizeof A); int maxp=0; for (int i=0;i<n;i++){ LL x;cin>>x; for (int j=0;j<h;j++)while (x%p[j]==0){ maxp=max(j,maxp);x/=p[j];A[j][i]^=1; } } int r=Rank(A,maxp+1,n); if (r>=n)printf("%d\n",0); else printf("%d\n",RP(2,n-r)-1); } return 0; }