http://acm.hdu.edu.cn/showproblem.php?pid=5833
问题概述：输入n个数，可以从当中选出一些数，使得这些数乘积为一个完全平方数，求出总共有多少种不同选法
（不能不选）（http://acm.hdu.edu.cn/showproblem.php?pid=5833）
输入样例： 对应输出：
2 Case #1:
3 3
3 3 4 Case #2:
3 3
2 2 2
高斯消元：
①对于n行m列增广矩阵，初始化p==q==1
②遍历第p行第q列及下面的所有元素，找到一个非0元，如果找到执行步骤③，没有找到q++，继续执行步骤②，直
到q超过m，执行步骤④
③将这一行和第p行交换，交换后再遍历p行q列下面的每一个元素，如果当前元值不为0，则通过行变换将这行所有
元素减去p行元素的一定比例，使得当前元为0，遍历完毕，p++，q++，继续执行步骤②
④矩阵已经化为阶梯形矩阵，矩阵的秩就是p-1， 方程组不同解的个数就是2^(n-p+1)
此题题解：
定理：每个平方数的质因子都有偶数个，而若干个数相乘就是将它们的质因数加在一起
设一个矩阵，矩阵中的元素a[i][j]==0表示第i个元素可以分解出偶数个第j个质因数，a[i][j]==1表示第i个元素可以分解
出奇数个第j个质因数，而这题可以将这个矩阵看做成一个方程组的系数矩阵，且这个方程组每一个方程都等于0，
又因为这道题不允许一个数不选，所以矩阵的全0解非法！最后的答案便是方程组解的个数-1
附录：线性方程组解的判断：
设矩阵A为系数矩阵，列向量b为方程对应的值，矩阵B=(A,b)（增广矩阵），n为未知数的个数（列数）
则有：①R(A)<R(B) ------ 无解
②R(A)==R(B)==n ------ 有一个解
③R(A)==R(B)<n ------ 有多个解
PS：当b为0向量时，方程组为线性齐次方程组，不可能无解（像这道题就是个01线性齐次方程组）
#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; #define mod 1000000007 int pri[2100], a[2100] = {1,1}; int solve(int A[][305], int n, int m); int main(void) { int T, i, j, k, n, mxj, cas, ans, ret, A[305][305]; long long x; k = 0; for(i=2;i<=2000;i++) { if(a[i]==1) continue; pri[++k] = i; for(j=i*i;j<=2000;j+=i) a[j] = 1; } scanf("%d", &T); cas = 1; while(T--) { mxj = 0; scanf("%d", &n); memset(A, 0, sizeof(A)); for(i=1;i<=n;i++) { scanf("%lld", &x); for(j=1;j<=k;j++) { while(x%pri[j]==0) { mxj = max(mxj, j); x /= pri[j]; A[j][i] ^= 1; } } } ret = solve(A, mxj, n); ans = 1; for(i=1;i<=n-ret;i++) ans = (ans*2)%mod; printf("Case #%d:\n%d\n", cas++, ans-1); } return 0; } int solve(int A[][305], int n, int m) { int i, j, p, r, q; p = q = 1; while(p<=n && q<=m) { r = -1; for(i=p;i<=n;i++) { if(A[i][q]) r = i; } if(r==-1) { q++; continue; } for(i=1;i<=m;i++) swap(A[r][i], A[p][i]); for(i=p+1;i<=n;i++) { if(A[i][q]) { for(j=q;j<=m;j++) A[i][j] ^= A[p][j]; } } p++, q++; } return p-1; }
