HDU 5833 Zhu and 772002

题目在这里>_<

题意

给你$n$个数，每个数的质因数不会超过2000。
每个数至多选一次，不能都不选。
求选其中一些数使得其乘积为完全平方数的方案数。

思路

乘积为完全平方数意味着其每个质因数的次数为偶数个。
2000以内的质因数有303个，我们可以建立一个矩阵$A$.
$a_{ij}$代表选第$j$个数能否贡献出一个第$i$个质因数。
那么我们对其高斯消元求秩，就可以得到其中有多少个自由变量。
因此也就得到解的个数，即方案数。

代码

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <iostream>
#include <map>
#include <set>
//#define test
using namespace std;
const int Nmax=2001;
typedef long long ll;
const ll mod=1e9+7LL;
int n;
int ans[Nmax][Nmax];
int size;
int prime[Nmax];
int is_prime[Nmax];
int prime_cnt;

void get()
{
    for(int i=2;i<Nmax;i++)
        is_prime[i]=1;
    for(long long i=2;i<Nmax;i++)
    {
        if(is_prime[i])
            prime[++prime_cnt]=i;
        for(int j=1;j<=prime_cnt;j++)
        {
            if(i*prime[j]>=Nmax)
                break;
            is_prime[i*prime[j]]=0;
            if(i%prime[j]==0)
                break;
        }
    }
}

void init()
{
    size=0;
    memset(ans,0,sizeof(ans));
}
int Rank(int n,int m,int a[][Nmax])
{//异或版的高斯消元求秩
    int i=1,j=1,k,idx,u;
    while(i<=n&&j<=m)
    {
        idx=i;
        while(a[idx][j]==0&&idx<=n)
            idx++;
        if(a[idx][j])
        {
            swap(a[i],a[idx]);
            for(u=i+1;u<=n;u++)
            {
                if(a[u][j])
                {
                    for(k=i;k<=m;k++)
                        a[u][k]^=a[i][k];
                }
            }
            i++;
        }   
        j++;
    }
    return i-1;
}

void show()
{
    for(int i=1;i<=5;i++)
        for(int j=1;j<=n+1;j++)
            printf("%d%c",ans[i][j],j==n+1?'\n':' ');
}
void work(ll x)
{
    ++size;
    for(int i=1;i<=prime_cnt;i++)
    {
        if(x%prime[i]==0)
        {
#ifdef test
            printf("x:%d,prime[%d]:%d\n",size,i,prime[i]);
#endif
            int t=0;
            while(x%prime[i]==0)
            {
                x/=prime[i];
                t^=1;
            }
            ans[i][size]=t;        
        }
    }
}
ll qpow(ll base,ll n)
{
    base%=mod;
    ll ans=1LL;
    while(n>0)
    {
        if(n&1)
            ans=ans*base%mod;
        base=base*base%mod;
        n>>=1;
    }
    return ans;
}
int main()
{
    #ifdef test
    freopen("m.in","r",stdin);
    #endif
   freopen("m.in","r",stdin);
    int t;
    get();
    scanf("%d",&t);
    #ifdef test
    printf("prime:%d\n",prime_cnt);
    for(int i=1;i<=10;i++)
        printf("%d\n",prime[i]);
    #endif
    for(int cases=1;cases<=t;cases++)
    {
        printf("Case #%d:\n",cases);
        init();
        scanf("%d",&n);
        ll x;
        for(int i=1;i<=n;i++)
        {
            scanf("%lld",&x);
            work(x);
        }
    #ifdef test
        show();
    #endif
        int tmp=Rank(prime_cnt,n,ans);
    #ifdef test
        printf("rank:%d\n",tmp);    
    #endif
        ll num=1LL*n-tmp;
    #ifdef test
        //printf("after:\n");
        //show();
    #endif
        num=qpow(2LL,num);
        num--;
        printf("%lld\n",num);
    }
    return 0;
}