ACM高斯消元法 亦或方程组求秩 （HDU5833 Zhu and 772002）

今天第一次接触高斯消元的题目，如果没有学习线性代数，估计这里很难学会

题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=5833

Problem Description Zhu and 772002 are both good at math. One day, Zhu wants to test the ability of 772002, so he asks 772002 to solve a math problem.

But 772002 has a appointment with his girl friend. So 772002 gives this problem to you.

There are n

numbers a

1

,a

2

,...,a

n

. The value of the prime factors of each number does not exceed 2000

, you can choose at least one number and multiply them, then you can get a number b

.

How many different ways of choices can make b

is a perfect square number. The answer maybe too large, so you should output the answer modulo by 1000000007

.  

Input First line is a positive integer T

, represents there are T

test cases.

For each test case:

First line includes a number n(1≤n≤300)

，next line there are n

numbers a

1

,a

2

,...,a

n

,(1≤a

i

≤10

18

)

.  

Output For the i-th test case , first output Case #i: in a single line.

Then output the answer of i-th test case modulo by 1000000007

.

【解析】：

本题的每一个数字可以分解为质因数相乘的形式，比如24=2^(2)*3^(2)。

然后列一个表格（纵向为素数，横向为原数列，表格中填质因数的指数，没填的为0）：

可以发现，任意几列相加，只要和还是偶数，上面的数乘起来就是完全平方数。

然后就可以转化一下，偶数全化为0，不影响奇偶性。

然后就可以写成方程组形式：

0*x1 + 0*x2 + 0*x3 + 0*x4 = 0;

1*x1 + 1*x2 + 0*x3 + 1*x4 = 0;

然后方程组的系数就是上述表格，写成矩阵，即增广矩阵，只要求出这个矩阵的秩，就确定了不自由变量的数目z，

用总变元数目n减去z，就得到了自由变量的数目n-z。

因为每个自由变量只有0,1两种选择，所以总共解的数量：2^(n-z)

对于本题，记得减掉全为0的一种情况

【代码】：

#include <stdio.h>  
#include <string.h>    
#include <iostream>    
#include <algorithm>   
#define set(a,i)  memset(a,i,sizeof(a))  
using namespace std;  
typedef long long ll;  
const int mod=1e9+7;  
ll qpow(ll n,ll m){n%=mod;ll ans=1;while(m){if(m%2)   
        ans=(ans*n)%mod;m/=2;n=(n*n)%mod;}return ans;}  
int pri[500],top;//pri存素数   
bool v[2100];  
void prime()//素数打表   
{  
    top=1;  
    set(v,true);//假设素数  
    for(int i=2;i<2003;i++)  
    {  
        if(v[i]){  
            pri[top++]=i;  
            for(int j=i+i;j<2003;j+=i)  
                v[j]=false;  
        }  
    }  
}  
int T,n,r;  
int a[502][502];//以下运算下标从1开始   
int huajian2(int n,int m)//亦或矩阵的化简  
{
	int row=1;
    for(int col=1,i;col<=m;col++)//列  
    {  
        for(i=row;i<=n;i++)if(a[i][col])break;  
        if(i>n)continue;//本列不处理   
        if(i!=row){  
            for(int j=col;j<=m+1;j++)  
                swap(a[i][j],a[row][j]);
        }  
        for(i=row+1;i<=n;i++)  
        {  
            if(a[i][col])//i行需被消掉  
            {  
                int now=a[row][col],next=a[i][col];  
                int lcm=now*next/__gcd(now,next);  
                int w=lcm/now,t=lcm/next;  
                for(int j=col;j<=m+1;j++)  
                    a[i][j]=a[row][j]^a[i][j];
            }   
        }  
        row++;//别忘了   
    }  
    return row-1;//秩 
}  
int main()  
{  
    prime();  
    scanf("%d",&T);  
    while(T--)  
    {  
        scanf("%d",&n);  
        set(a,0);  
        for(int i=1;i<=n;i++)  
        {  
            ll num;  
            scanf("%lld",&num);  
            int p=1;  
            while(num!=1)  
            {  
                while(num%pri[p])p++;  
                num/=pri[p];  
                a[p][i]^=1;//增广矩阵 
            }  
        }  
        int z=huajian2(top,n);//把矩阵化简，求秩z  
        printf("Case #%d:\n",++r);  
        printf("%lld\n",(mod+qpow(2,n-z)-1)%mod);//n-z就是自由变元的个数   
    }  
    return 0;  
}