【题意】给出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;
}