http://acm.hdu.edu.cn/showproblem.php?pid=5833 给你n个数组，n最大300，然后每个数字都是只有2000以内的素因子，让你选一些数字乘起来，是完全平方数，方案数 因为2000以内只有304个素因子，然后完全平方数就是这个素因子出现了偶数次，就是模2，所以可以看成模2的同余方程组，对于每个素因子，列一行方程 用开关问题的高斯消元即可解决，然后就是找自由变元的个数，对自由变元赋值，即可求出其他的变元，所以自由变元有x个，就有2x个解，但是全0的时候，其他变元也都是0，所以应该是2x−1个解
代码：
#include <map> #include <set> #include <stack> #include <queue> #include <cmath> #include <string> #include <vector> #include <cstdio> #include <cctype> #include <cstring> #include <sstream> #include <cstdlib> #include <iostream> #include <algorithm> #pragma comment(linker,"/STACK:102400000,102400000") using namespace std; #define MAX 405 #define MAXN 1000005 #define maxnode 205 #define sigma_size 26 #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define lrt rt<<1 #define rrt rt<<1|1 #define middle int m=(r+l)>>1 #define LL long long #define ull unsigned long long #define mem(x,v) memset(x,v,sizeof(x)) #define lowbit(x) (x&-x) #define pii pair<int,int> #define bits(a) __builtin_popcount(a) #define mk make_pair #define limit 10000 //const int prime = 999983; const int INF = 0x3f3f3f3f; const LL INFF = 0x3f3f; const double pi = acos(-1.0); const double inf = 1e18; const double eps = 1e-4; const LL mod = 1e9+7; const ull mx = 133333331; /*****************************************************/ inline void RI(int &x) { char c; while((c=getchar())<'0' || c>'9'); x=c-'0'; while((c=getchar())>='0' && c<='9') x=(x<<3)+(x<<1)+c-'0'; } /*****************************************************/ int A[MAX][MAX],free_x[MAX],x[MAX]; void init(){ mem(A,0); mem(free_x,0); mem(x,0); } int check(int n,int m,int r){ for(int i=r-1;i>=0;i--){ int k; for(k=0;k<m;k++) if(A[i][k]) break; x[k] = A[i][m]; for(int j=k+1;j<m;j++) x[k] ^= (x[j] & A[i][j]); } int ans = 0; for(int i=0;i<m;i++) if(x[i]) ans++; return ans; } int Gauss(int n,int m){ int r,c; for(r=0,c=0;r<n && c<m;c++){ int maxr = r; for(int i=r+1;i<n;i++) if(abs(A[i][c]) > abs(A[maxr][c])) maxr = i; if(maxr != r) for(int i=c;i<=m;i++) swap(A[maxr][i],A[r][i]); if(!A[r][c]){ free_x[c] = 1; continue;} for(int i=0;i<n;i++) if(i!=r&&A[i][c]){ for(int j=c;j<=m;j++) A[i][j] ^= A[r][j]; } r++; } for(int i=r;i<n;i++) if(A[i][m]) return -1; //下面是枚举自由变元的值，使得解为1的个数尽量少的求解过程 int val = 0,ans = INF; for(int i=0;i<m;i++) if(free_x[i] == 1) val++; return val; /*for(int i=0;i<(1<<val);i++){ int cnt = 0; for(int j=0;j<m;j++) if(free_x[j]){ if((1<<cnt) & i) x[j] = 1; else x[j] = 0; cnt++; } if(bits(i) >= ans) continue; ans = min(ans,check(n,m,r)); } return ans;*/ } int prime[2005]; int pr[2005]; int tot; void priinit(){ mem(prime,0); tot=0; for(int i=2;i<=2000;i++){ if(!prime[i]){ for(int j=2*i;j<=2000;j+=i) prime[j]=1; pr[tot++]=i; } } } int main(){ //freopen("in.txt","r",stdin); int t,kase=0; cin>>t; priinit(); //cout<<tot<<endl; while(t--){ kase++; int n; cin>>n; init(); for(int i=0;i<n;i++){ LL a; scanf("%I64d",&a); for(int j=0;j<tot;j++){ if(a%pr[j]==0){ while(a%pr[j]==0){ A[j][i]++; a/=pr[j]; } A[j][i]%=2; } } //cout<<a; } int cnt=Gauss(tot,n); LL ans=1; for(int i=0;i<cnt;i++){ ans=ans*2%mod; } printf("Case #%d:\n%I64d\n",kase,(ans-1+mod)%mod); } return 0; }