UVA11524构造系数数组+高斯消元解异或方程组

  1 /*UVA11524
  2 题目：给定n个数(n<=100)，从中找出1或多个数，使他们的乘积是一个完全平方数
  3 分析：转化成数理模型是第一步，肯定要分解质因数，ps：题目给定不含大于500的素因子。
  4 第二选择的数字相同质因子个数之和必须是偶数，因为之奇偶性有关，可将奇数为1，偶数为0，这样约简。
  5 然后按照常理，应该找出所有的可能性（暴力的思想），因为n<=100，不可能用状态压缩的办法，所以用下面的方法，同时也是给自己一个拓展的思路
  6 高斯消元解异或方程组：
  7 假设n个数，设数组ch[i]，表式选第i的数与否，那么，列出每个质因子的总个数方程，总个数模2为0即可，因为异或等同于模2加，故列异或方程。
  8 最后自由变量假设有k个，则说明2^k-1种方案
  9 解异或方程组的思路：
 10 1、构造系数数组（0,1）
 11 Mat[i][j]:第i个质因数的方程，第j个数字的因数分解后的个数
 12 2、解异或方程Mat(n,m)//要收录
 13 
 14 int solve(int n1,int m1) //解方程部分借鉴白书，要弄明白
 15 {
 16     int i=0,j=0;
 17     while(i<n1&&j<m1)
 18     {
 19         int r=i;
 20         for(int k=i; k<n1; k++)
 21             if (A[k][j])
 22             {
 23                 r=k;
 24                 break;
 25             }
 26         if (A[r][j])
 27         {
 28             if (r!=i) for(int k=0; k<=m1; k++) swap(A[r][k],A[i][k]);
 29             for(int u=i+1; u<n1; u++) if (A[u][j])
 30                     for(int k=i; k<=m1; k++) {A[u][k]^=A[i][k];}
 31             i++;
 32         }
 33         j++;
 34     }
 35     return i;
 36 }//返回的是确定解的个数
 37 */
 38 #include<iostream>
 39 #include<stdio.h>
 40 #include<string.h>
 41 #include<algorithm>
 42 #include<stdlib.h>
 43 #include<math.h>
 44 #include<queue>
 45 #include<vector>
 46 #include<map>
 47 //#define LL long long
 48 using namespace std;
 49 
 50 bool isprim[505];
 51 int cnt;
 52 int prim[505/2];
 53 void prime_calc()
 54 {
 55     cnt=0;
 56     memset(isprim,0,sizeof(isprim));
 57     for(int i=2; i<=500; i++)
 58     {
 59         if (!isprim[i])
 60         {
 61             prim[cnt++]=i;
 62             for(int j=2*i; j<=500; j+=i) isprim[j]=1;
 63         }
 64     }
 65 }
 66 
 67 int T,n;
 68 int A[505][505];
 69 
 70 int solve(int n1,int m1) //解方程部分借鉴白书，要弄明白
 71 {
 72     int i=0,j=0;
 73     while(i<n1&&j<m1)
 74     {
 75         int r=i;
 76         for(int k=i; k<n1; k++)
 77             if (A[k][j])
 78             {
 79                 r=k;
 80                 break;
 81             }
 82         if (A[r][j])
 83         {
 84             if (r!=i) for(int k=0; k<=m1; k++) swap(A[r][k],A[i][k]);
 85             for(int u=i+1; u<n1; u++) if (A[u][j])
 86                     for(int k=i; k<=m1; k++) A[u][k]^=A[i][k];
 87             i++;
 88         }
 89         j++;
 90     }
 91     return i;
 92 }
 93 
 94 int main()
 95 {
 96     prime_calc();
 97     cin>>T;
 98 //    cout<<cnt<<endl;
 99     while(T--)
100     {
101         cin>>n;
102         int n1=0,m1=n;
103         memset(A,0,sizeof(A));
104         long long  k;
105         for(int i=0; i<n; i++)
106         {
107             cin>>k;
108             for(int j=0; j<cnt; j++){
109                 while(k%prim[j]==0) {A[j][i]^=1;n1=max(n1,j+1);k=k/prim[j];}
110             }//构造系数矩阵，系数只和奇偶性有关
111         }
112         cout<<(1LL<<(n-solve(n1,m1)))-1<<endl;//注意pow运算处理不了LL的数据，要么手写函数，要么移位运算
113     }
114     return 0;
115 }