hdu5833----高斯消元

题目大意:

给你n个整数，从中选一些数，他们的乘积为一个完全平方数

问有多少种这样的方式,已知这些数的素因素不超过2000.

思路：

一个完全平方数素因素的个数肯定是偶数个. 我们只要从n个数中选取所有的素因子的个数刚好能凑成偶数个。

先枚举2000内的素数，总共303个，相当于构造303个方程,然后我们可以把这n个数当做方程组的n个变量，

当然取值只能为0,1(选与不选),系数矩阵就是这n个数对于这303个素数中的每个素数有多少个。

A[1][2]:代表第二个数的因子中有多少个2(2是第一个素数),如果偶数个则取值为0,奇数个则为1

最后高斯消元求出自由变元的个数k，答案就是2^k-1;因为每个自由变元的取值为0或1,要排除全为0的情况.

对于样例3 3 4,答案为3

3=1*3,4=2*2;

A[1][1]=0,A[1][2]=0,A[1][3]=0; 素数2

A[2][1]=1,A[2][2]=1,A[2][3]=0；素数3

A[k][1]=0,A[k][2]=0,A[k][3]=0;(k>3)没有其他素数了，所以全为0

相当于求方程 (0*x1+0*x2+0*x3)=2k;

(x1+x2+0*x3)=2K;

转变为一个异或方程组：只要使得每个方程系数为1的是偶数个就行了,系数为0的不用管

x1^x2=0 x1=x2=0,1 x3=0,1去掉0,0,0这种情况

代码如下：

#include <iostream>

#include<cmath>

#include<cstring>

#include<cstdio>

using namespace std;

#define MOD 1000000007

const int maxs = 310;

const int N = 2000+1;

int n;

__int64 a[maxs];

int A[maxs][maxs];

int prime[maxs],counts;

void getPrime()

{

    bool vis[N];

    counts=0;

    memset(vis,true,sizeof(vis));

    int len = (int)sqrt(N-1+0.5);

    for(int i=2;i<=len;i++)

    {

        int j=i*i;

        for(;j<N;j=j+i)

            vis[j]=false;

    }

    for(int i=2;i<N;i++)

        if(vis[i])

            prime[++counts]=i;

}

void init()

{

    for(int i=1;i<=counts;i++)

        for(int j=1;j<=n;j++)

            while(a[j]%prime[i]==0)

            {

                A[i][j]^=1;

                a[j]/=prime[i];

            }

}

int gaosi(int equ,int var)

{

    int k,col;

    for(k=1,col=1;k<=equ&&col<=var;k++,col++)

    {

        int max_r=k;

        int maxValue=abs(A[k][col]);

        for(int i=k+1;i<=equ;i++)

            if(abs(A[i][col])>maxValue)

            {

                maxValue=abs(A[i][col]);

                max_r=i;

            }

        if(max_r!=k)

        {

            //交换两行

            for(int i=1;i<=var;i++)

                swap(A[k][i],A[max_r][i]);

        }

        if(A[k][col]==0)

        {

            k--;continue;

        }

        for(int i=k+1;i<=equ;i++)

        {

            if(A[i][col]!=0)

            {

                for(int j=col;j<=var;j++)

                    //原来这里是异或运算，无限wa

                    A[i][j]^=A[k][j];

            }

        }

    }

    k=k-1;

    return var-k;//自由变元的个数

}

__int64 mutimod(__int64 a,__int64 n,__int64 m)

{

    __int64 ans=1;

    while(n)

    {

        if(n&1LL)//判断是否为奇数

            ans=ans*a%m;

        n>>=1LL;

        a=a*a%m;

    }

    return ans;

}

int main()

{

    //freopen("in.txt","r",stdin);

    getPrime();

    int T;

    cin>>T;

    for(int t=1;t<=T;t++)

    {

        memset(A,0,sizeof(A));

        cin>>n;

        for(int i=1;i<=n;i++)

            scanf("%I64d",&a[i]);

        init();

        int freeNum = gaosi(counts,n);

        __int64 ans = mutimod(2,freeNum,MOD);

        printf("Case #%d:\n%I64d\n",t,ans-1);

    }

    return 0;

}

巴特西

hdu5833----高斯消元

最新文章

热门文章