HDU - 5833: Zhu and 772002 (高斯消元-自由元)

pro：给定N个数Xi(Xi<1e18)，保证每个数的素因子小于2e3；问有多少种方案，选处一些数，使得数的乘积是完全平方数。求答案%1e9+7； N<300;

sol：小于2e3的素数只有304个。选或者不选看成1和0，那么问题其实就是问%2意义下的自由元。 答案是2^自由元

#include<bits/stdc++.h>

#define ll long long

#define rep(i,a,b) for(int i=a;i<=b;i++)

using namespace std;

const int maxn=;

const int Mod=1e9+;

int a[][],vis[maxn],p[],tot;

void prime()

{

    for(int i=;i<maxn;i++){

        if(!vis[i]) p[tot++]=i;

        for(int j=;j<=tot&&p[j-]*i<maxn;j++){

            vis[i*p[j-]]=;

            if(i%p[j-]==) break;

        }

    }

}

int Gauss(int N,int M)

{

    int free=;

    for(int i=,p=;i<N&&p<M;i++,p++){

        int t=i;

        rep(j,i+,N-) if(a[j][p]>a[t][p]) t=j;

        if(!a[t][p]){ i--; free++; continue;}

        if(i!=t) rep(j,p,M) swap(a[i][j],a[t][j]);

        rep(j,i+,N-){

            if(!a[j][p]) continue;

            rep(k,p,M) a[j][k]^=a[i][k];

        }

    }

    return free;

}

int main()

{

    prime();

    int T,N,num,C=; ll x;

    scanf("%d",&T);

    while(T--){

        memset(a,,sizeof(a));

        scanf("%d",&N);

        rep(i,,N-) {

            scanf("%lld",&x);

               rep(j,,tot-){

                ll tx=x;

                while(tx%p[j]==){

                    tx/=p[j]; a[j][i]^=;

                }

            }

        }

        int t=Gauss(tot,N);

        int res=;

        rep(i,,t) res=res*%Mod;

        printf("Case #%d:\n%d\n",++C,(res+Mod-)%Mod);

    }

    return ;

}