高斯消元——01异或方程组

题目大意

给一个集合，问有多少个子集满足这样的条件：子集内的元素之积可以开方。UVA-11542。

样例输入

4
3
2 3 5
3
6 10 15
4
4 6 10 15
3
2 2 2

样例输出

0
1
2
3

题目分析

可以将集合里的每个数拆成素数之积，比如第三组，4 = 2^2 ，6 = 2^1 * 3^1 ， 10 = 2^1 * 5^1 ， 15 = 3^1 * 5^1 。
能拆出来的素数因子有三个，就列三个方程，将4,6,10,15这四个数记做X1，X2，X3，X4。他们取1代表要选这个数字。
他们取0等于不选这个数字。
对于素数因子2 ： 2X1 + 1X2 + 1X3 + 0X4 = 0
对于素数因子3 ： 0X1 + 1X2 + 0X3 + 1X4 = 0
对于素数因子5 ： 0X1 + 0X2 + 1X3 + 1X4 = 0

由于要使得最终的积可以开根，所以每个因子的指数得是偶数。
所以可以把系数模2得到：

对于素数因子2 ： 0X1 + 1X2 + 1X3 + 0X4 = 0
对于素数因子3 ： 0X1 + 1X2 + 1X3 + 0X4 = 0
对于素数因子5 ： 0X1 + 0X2 + 1X3 + 1X4 = 0

矩阵：
0 1 1 0 0
0 1 0 1 0
0 0 1 1 0

然后将它异或消元。跟高斯消元类似，只不过不是每行相减，而是每行异或。

解出来的话，先找到方程自由变量的个数，因为自由变量代表可以等于0或1。就是可以选也可以不选。
一共就有2^tmp(自由变量) ， 这么多种情况。除掉 一种全都不选的情况就是答案。

代码如下

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<map>
#include<queue>
#include<vector>
#include<cmath>
#define CLR(x) memset(x,0,sizeof(x))
#define LL long long
using namespace std;
int prime[1000];
int vis[1000];
int mat[505][505];
int n;
int maxr;

int Pri(){
    for(int i = 2 ; i <= 25 ; i++)
        for(int j = i*i ; j <= 625 ; j += i)
            vis[j] = 1;
    int con = 0;
    for(int i = 2 ; i <= 500 ; i++){
        if(vis[i] == 0){
            prime[con] = i;
            con++;
        }
    }
    return con;
}

void debug()
{
    printf("\n");
    for(int i = 0 ; i < maxr+1 ; i++){
        for(int j = 0 ; j < n ; j++){
            printf("%d ",mat[i][j]);
        }
        printf("\n");
    }
    printf("\n");
}

int guass(){
    int r = maxr + 1;
    int c = n;
    int i = 0 , j = 0;
    while(i<r&&j<c){
        int tmp = i;
        for(int k = i ; k < r ;k++){
            if(mat[k][j]) tmp = k;
        }
        if(mat[tmp][j]){
            if(tmp!=i){
                for(int k = 0 ; k < c ;k++) swap(mat[i][k],mat[tmp][k]);
            }
            for(int k = i+1 ; k < r ; k++){
                if(mat[k][j]){
                    for(int u = 0 ; u < c ; u++){
                        mat[k][u] ^= mat[i][u];
                    }
                }
            }
            i++;
        }
        j++;
    }
    return n-i;
}

int main()
{
    int cas;
    scanf("%d",&cas);
    int num = Pri();
    while(cas--){
        CLR(mat);
        maxr = 0;
        scanf("%d",&n);
        for(int i = 0 ; i < n ; i++){
            LL x;
            scanf("%lld",&x);
            for(int j = 0 ; j < num ; j++){
                int tmp = prime[j];
                //bool flag = false;
                while(x%tmp == 0){
                    x/=tmp;
                    maxr = max(maxr,j);
                    mat[j][i] ^= 1;
                    //if(x == 1){flag = true ; break;}
                }
                //if(flag) break;
            }

        }
        int ans = guass();
        //debug();

        printf("%lld\n",(1LL<<ans)-1);
    }
}