【HDU 5833】Zhu and 772002（异或方程组高斯消元讲解）

题目大意：给出n个数字a[]，将a[]分解为质因子（保证分解所得的质因子不大于2000）,任选一个或多个质因子，使其乘积为完全平方数。求其方法数。

学长学姐们比赛时做的，当时我一脸懵逼的不会搞……所以第二天上午花了一上午学习了一下线性代数。

题目思路：

任选一个或多个质因子，起乘积为完全数m，因为组成它的均为素数，假设组成m的素数的种类为n，那么这n类素数中每类素数的个数应为偶数。

可设：a[i][j]=0代表第i种素数可在a[j]中分离出的个数为偶数，a[i][j]=1代表第i种素数可在a[j]中分离出的个数为奇数数。

b[i]=1代表选择这类素数，b[i]=0代表不选择这类素数。

列出线性方程组：

a₁₁x₁+a₁₂x₂+...+a_1nx_n=0

a₂₁x₁+a₂₂x₂+...+a_2nx_n=0

...

a_n1x₁+a_n2x₂+...+a_nnx_n=0

求解的个数 ans

转化为矩阵形式：

矩阵A=

a11 a12 a13 …………a1n

a21 a22 a23 …………a2n

……………………………………

an1 an2 an3 …………ann

通过初等变换可将矩阵A换成类似下面矩阵B的形式

a11 a12 a13 ……a1n

0 a22 a23 ……a2n

0 0 a33……a3n

0 0 0 ……arn

再将矩阵B转化成线性方程组可求出最后一组方程的解，倒着往回求可求出所有方程解

可解出的方程组共 r 个，由秩的定义可知 r等矩阵A的秩

由定理：

对于n元齐次线性方程组如果r<n，则方程组含n-r个自由未知量。

解的个数ans=2^（n-r）-1(减去全0解)

具体操作：

#include<cstdio>
#include<stdio.h>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#define INF 0x3f3f3f
#define MAX 2105
#define MOD 1000000007

using namespace std;

long long c[MAX][505],p[MAX],v[MAX],a[MAX],cnt,n;//c存矩阵，p存素数表，cnt代表素数的个数

void MakeTab()//打素数表
{
    int i,j;
    memset(v,0,sizeof(v));
    memset(p,0,sizeof(p));
    cnt=0;
    for(i=2; i<=2000; i++)
    {
        if(!v[i])
        {
            p[++cnt]=i;
            for(j=i; j<=2000; j+=i)
            {
                v[j]=1;
            }
        }
    }
}

int Rank()//计算秩
{
    int i,j,k,r,u;
    i=0;
    j=0;
    while(i<=cnt && j<=n)
    {
        r=i;
        while(!c[r][j] && r<=cnt)
            r++;
        if(c[r][j])
        {
            swap(c[i],c[r]);//如果发现了第r行第j列为1，就讲r行和i行行互换（初等行变换）
            for(u=i+1; u<=cnt; u++)
            {
                if(c[u][j])
                {
                    for(k=i; k<=n; k++)
                    {
                        c[u][k]=c[u][k]^c[i][k];//每找到一个未知数就对其进行亦或处理，去掉系数c[i][k]
                    }

                }
            }
            i++;
        }
        j++;
    }
    return i;
}

int main()
{
    MakeTab();
    int i,j,cns=1,T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%lld",&n);
        memset(c,0,sizeof(c));
        for(i=1; i<=n; i++)
        {
            scanf("%lld",&a[i]);
        }

        for(i=1; i<=n; i++)
        {
            for(j=1; j<=cnt; j++)
            {
                long long num=a[i];
                if(num%p[j]==0)
                {
                    while(num%p[j]==0)
                    {
                        num/=p[j];
                        c[j][i]=c[j][i]^1;
                    }
                }
            }
        }

        long long k=(n-Rank());
        long long ans=1;
        for(i=1; i<=k; i++)
            ans=(ans*2)%MOD;
        printf("Case #%d:
",cns++);
        printf("%lld
",ans-1);//去掉全0的解
    }
    return 0;
}

View Code