UVa11542

题目链接

分析：
题目特意说到，不含有超过500的素因子
这就是在提示我们可以质因数分解
我们把这n个数分解成若干素数乘积的形式，并用一个向量表示

如：4 6 10 15
这n=4个数中，涉及到的素数只有2,3,5这三个
分解后：
4=2^2*3^0*5^0 ——>{2,0,0}
6=2^1*3^1*5^0 ——>{1,1,0}
10=2^1*3^0*5^1 ——>{1,0,1}
15=2^0*3^1*5^1 ——>{0,1,1}

我们现在按照题目要求，选出若干数乘起来，
得到的数字（我们称为W）也一定可以用2,3,5这三个质数表示

为了辅助该数的表示，我们设一个01向量x
xi表示第i位数字是否要选（选是1，不选是0）
这样我们按照题目求出的数就可以如下表示了：

因为只有第一个数（4），第二个数（6），第三个数（10）有2这个因子，
所以得到的W中2的指数只能由这三个数决定，其余的同理

如果W可以被开方，显然每个质数的次数都要是偶数，即
x2+x3=0 (mod 2)
x2+x4=0 (mod 2)
x3+x4=0 (mod 2)
由于异或和数字的奇偶性有很大关系，所以上述的方程组可以变成异或方程
x2 XOR x3=0
x2 XOR x4=0
x3 XOR x4=0

这样我们就可用高斯消元优美的解决了

最后的答案是

2^（自由元的个数）-1

因为每个自由元都有两种选择，但是题目不允许我们一个都不选，所以要-1

tip

在阵式的构造上，
a[i][j]=1表示第j个数字有第i个质数这个因子，且该因子在第j个数中的次数是奇数，
换句换说就是，第i个质数的次数会受到第j个数的影响

gauss消元没有固定的模板，重要的是掌握ta的思维方式

//这里写代码片
#include<cstdio>
#include<cstring>
#include<iostream>
#define ll long long

using namespace std;

int a[102][102];     //500以内的素数只有95个  
int sshu[102],tot=0,maxp,n; 
bool no[502];

void prime(int n)
{
    for (int i=2;i<=n;i++)
    {
        if (!no[i]) sshu[++tot]=i;
        for (int j=1;j<=tot&&sshu[j]*i<=n;j++)
        {
            no[sshu[j]*i]=1;
            if (i%sshu[j]==0) break;
        }
    }
}

int gauss(int n,int m)                     //n个未知量，m个方程 
{
    int cnt=0;
    int now=1;
    for (int i=1;i<=n;i++)                 //枚举未知量 
    {
        int num=now;                       //消元消到了第几个方程 
        for (int j=now;j<=m;j++) 
            if (a[j][i])
            {
                num=j;
                break;
            }
        if (!a[num][i]) continue;
        if (now!=num)
            for (int j=1;j<=n+1;j++)
                swap(a[now][j],a[num][j]);
        for (int j=1;j<=m;j++) 
            if (a[j][i]&&j!=now)
                for (int k=1;k<=n+1;k++)
                    a[j][k]^=a[now][k];
        now++;
    }
    return n-now+1;
}

int main()
{
    prime(500);
    int T;
    scanf("%d",&T);
    while (T--)
    {
        memset(a,0,sizeof(a));
        scanf("%d",&n);
        ll x;                                  //注意x的范围 
        maxp=0;                                //n个数中涉及到的最大素数 
        for (int i=1;i<=n;i++)
        {
            scanf("%lld",&x);
            for (int j=1;j<=tot&&x!=1;j++)
                while (x%sshu[j]==0)
                {
                    a[j][i]^=1;                //sshu[j]的系数可能有第i个数的影响 
                    x/=sshu[j];
                    maxp=max(maxp,j);
                }
        }

        int ans=gauss(n,maxp);
        printf("%lld
",(1LL<<ans)-1); 
    }
    return 0;
}