HDU 5833 Zhu and 772002（高斯消元）

题意：给n个数，从n个数中抽取x(x>=1)个数，这x个数相乘为完全平方数，求一共有多少种取法，结果模1000000007。

思路：每个数可以拆成素数相乘的形式，例如:

　x1　　　2=2^1 * 3^0 * 5^0;

　x2　　　3=2^0 * 3^1 * 5^0;

　x3　　　4=2^2 * 3^0 * 5^0;

　x4　　　5=2^0 * 3^0 * 5^1;

　x5　　　6=2^1 * 3^1 * 5^0;

　x6　　 15=2^0 * 3^1 * 5^1;

用xi表示第i个数选或不选，xi的取值为0或1；因为相乘结果为完全平方数，所以最后的完全平方数表示成素数相乘的形式后，每个素数的幂一定是偶数，即模2等于0:

　2　　　(x1+2*x3+x5)%2=0

　3　　　(x2+x5+x6)%2=0

　5　　　(x4+x6)%2=0

将上面的式子转化为异或方程组，求解有m个自由变量，每个自由变量都可以取0或1，最终答案为2^m-1（去掉全0的情况）;

#include <bits/stdc++.h>

using namespace std;

#define MAXN 2000

int prime[MAXN+];

int a[MAXN+][];

int free_num;

int free_x[MAXN];

int x[];

int equ,var;

const int mod=;

void getprime()

{

    int i,j;

    memset(prime,,sizeof(prime));

    prime[]=prime[]=;

    for(i=;i<=MAXN;i++)

    {

        if(prime[i])

            prime[++prime[]]=i;

        for(j=;j<=prime[]&&i*prime[j]<=MAXN;j++)

        {

            prime[i*prime[j]]=;

            if(i%prime[j]==)

                break;

        }

    }

}

void geta(int id,long long num)

{

    int i;

    i=;

    while(num!=)

    {

        while(num%prime[i]==)

        {

            num/=prime[i];

            a[i-][id]^=;

        }

        i++;

    }

}

//返回值为-1表示无解，为0是唯一解，否则返回自由变元个数

int Gauss()

{

    int max_r, col, k;

    free_num = ;

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

    {

        max_r = k;

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

            if(abs(a[i][col]==)

            {

                max_r = i;

                break;

            }

        if(a[max_r][col] == )

        {

            k--;

            free_x[free_num++] = col; //自由变元

            continue;

        }

        if(max_r != k)

        {

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

                swap(a[k][j],a[max_r][j]);

        }

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

            if(a[i][col] != )

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

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

    }

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

        if(a[i][col] != )

            return -;

    if(k < var)return var-k;

    return ;

}

int main()

{

    int ans;

    int t;

    int n;

    int i;

    int cas;

    int freex;

    long long num;

    scanf("%d",&t);

    getprime();

    //printf("%d\n",prime[0]);

    for(cas=;cas<=t;cas++)

    {

        memset(a,,sizeof(a));

        scanf("%d",&n);

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

        {

            scanf("%I64d",&num);

            geta(i,num);

        }

        equ=prime[];

        var=n;

        freex=Gauss();

        //printf("::%d\n",freex);

        if(freex==-)

            ans=;

        else if(freex==)

            ans=;

        else

        {

            ans=;

            for(i=;i<freex;i++)

            {

                ans=(*ans)%mod;

            }

            ans--;

        }

        printf("Case #%d:\n%d\n",cas,ans);

    }

    return ;

}