思路：
和HDU 5833 一样，只不过这次uva数据稍微少一点而已！
通过这次题目懂得了，高斯消元 题目，消元都是小事，难点在于构造矩阵！
例如有4个数 4，6，10，15.
素因子只有2，3，5.
2,3,5
4 -> (2,0,0);
6 -> (1,1,0);
10 ->(1,0,1);
15-> (0,1,1);
因此可以构造一个对2取模的01方程组！
每一行是不同素因子，每一列是那个素因子的个数！来构成选出来的数的乘积！
消元求出自由元即可！
注意long long
#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<cstdlib> #include<vector> using namespace std; typedef long long ll; const int maxn = 500 + 5; int equ, var; int a[maxn][maxn]; int x[maxn]; int free_x[maxn]; int free_num; int vis[maxn]; vector<int >prime; int len_prime; int Gauss(){ int max_r,col,k; free_num = 0; for (k = 0, col = 0; k < equ && col < var; k++, col++){ max_r = k; for (int i = k+1; i < equ; i++){ if (abs(a[i][col]) > abs(a[max_r][col])) max_r = i; } if (a[max_r][col] == 0){ k--; free_x[free_num++] = col; continue; } if (max_r != k){ for (int j = col; j < var+1; j++) swap(a[k][j],a[max_r][j]); } for (int i = k+1; i < equ; i++){ if (a[i][col] != 0){ for (int j = col; j < var+1; j++) a[i][j] ^= a[k][j]; } } } for (int i = k; i < equ; i++) if (a[i][col] != 0) return -1; if (k < var)return var- k; for (int i = var-1; i >= 0; --i){ x[i] = a[i][var]; for (int j = i+1; j < var; j++) x[i] ^= (a[i][j] && x[j]); } return 0; } void init(){ int len = sqrt(maxn) + 1; for (int i = 2; i <= len; ++i) if (!vis[i]) for (int j = i*i; j < maxn; j+=i) vis[j] = 1; for (int i = 2; i < maxn; ++i)if (!vis[i])prime.push_back(i); len_prime = (int)prime.size(); } int main(){ init(); int T; scanf("%d",&T); while(T--){ int n; scanf("%d",&n); memset(a,0,sizeof a); for (int i = 0; i < n; ++i){ ll x; scanf("%lld",&x); for (int j = 0; j < len_prime; ++j){ int pri = prime[j]; while(x % pri == 0){ a[j][i] ^= 1; x/=pri; } if (x == 1)break; } } equ = len_prime; var = n; int t = Gauss(); printf("%lld\n",( 1ll << t )-1ll); } return 0; }
