首先，一个完全平方数的每个质因子的幂一定是偶数。对每个数进行质因数分解，令其中幂为奇数的系数为1即可。
#include<iostream> #include<cstring> #include<cstdio> #include<cmath> using namespace std; #define LL long long const int mod=1000000007; const int maxn=305; int n,m;//有n个方程,m个未知数 int a[maxn][maxn]; int x[maxn];//解集 bool free_x[maxn];//判断是否为自由变元 int free_num;//记录自由变元的个数 int gcd(int a,int b) { return b==0?a:gcd(b,a%b); } int lcm(int a,int b) { return a*b/gcd(a,b); } //返回-2表示有浮点数解，但无整数解；返回-1表示无解；返回fjfj0表示有唯一解；返回1表示有无穷个解 int gauss() { int i,j,k; int max_r;//当前这列绝对值最大的行 int col;//当前处理的列 int ta,tb; int LCM; int temp; int free_x_num; int free_index; col=0; for(k=0;k<n&&col<m;k++,col++) {//枚举当前处理的行 max_r=k; for(i=k+1;i<n;i++) { if(abs(a[i][col])>abs(a[max_r][col])) max_r=i; } if(max_r!=k) {//与第k行交换 for(j=k;j<m+1;j++) swap(a[k][j],a[max_r][j]); } if(a[k][col]==0) {//说明该col列第k行以下全都是0了，则处理当前行的下一列 k--; continue; } for(i=k+1;i<n;i++) {//枚举要删去的行 if(a[i][col]!=0) { LCM=lcm(abs(a[i][col]),abs(a[k][col])); ta=LCM/abs(a[i][col]),tb=LCM/abs(a[k][col]); if(a[i][col]*a[k][col]<0) ta=-tb;//异号的情况是两个数相加 for(j=col;j<m+1;j++) { a[i][j]=((a[i][j]*ta)%2-(a[k][j]*tb)%2+2)%2; } } } } for(i=k;i<n;i++) { if(a[i][col]!=0) return -1; } if(k<m) return m-k;//自由变元有m-k个 return 0; } int p[2016],vis[2016],cnt=0; void getprim() { for(int i=2;i<2016;i++) { if(!vis[i]) p[cnt++]=i; for(int j=i;j<2016;j+=i) { vis[j]=1; } } } 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 main() { int k,cas=0; LL y; scanf("%d",&k); getprim(); n=cnt; while(k--) { memset(a,0,sizeof a); memset(free_x,1,sizeof free_x); scanf("%d",&m); for(int i=0;i<m;i++) { scanf("%lld",&y); for(int j=0;j<n;j++) { int sum=0; if(y%p[j]==0) { while(y%p[j]==0) { sum++; y/=p[j]; } } if(sum&1) a[j][i]=1; } } free_num=gauss(); printf("Case #%d:\n%lld\n",++cas,powmod(2,free_num)-1); } return 0; }