推荐两个博客：
https://www.jianshu.com/p/888f2c2b31bc
https://blog.csdn.net/weixin_43871207/article/details/108395566

我基本上就是看了上面两个博客，将代码的解析完善的，第一个博客理论讲的好，第二个博客代码写的好，每一句话都是精髓，如果不懂的话，一定反复阅读。

#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stdlib.h>
typedef long long ll;
using namespace std;
typedef long long ll;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const ll N = 2005; //要找出2000以内的素数（一共303个）
ll a[2005][2005];//增广矩阵
ll x[2005];  //如果有唯一解，则计算解集，存到x数组中
ll freeX[N]; //标记是否为自由变元



ll prime[2005]; //用prime数组储存素数
bool vis[2005]; //vis数组，如果=1，则不是素数，如果!=1，则是素数，相当于一个标记函数
ll tot;         //tot为素数的个数

void init() //初始化 -》 将素数找出来，存入prime数组里面
{
    memset(vis, 0, sizeof(vis));
    vis[1] = vis[0] = 1; //1不是素数，0是素数
    tot = 0;
    for(ll i = 2; i < N; ++i)
    {
        if(vis[i]==0)
        {
            prime[tot++] = i;
            for(ll j = 2*i; j < N; j += i)
            {
                vis[j] = 1;
            }
        }
    }
}

void solve(ll id, ll n) //id是第几位数（从0开始），n是第几位数的数值，解决第几个数前面是1还是0的问题
{
    for(ll i = 0; i < tot; ++i) //tot为素数的个数
    {
        while(n % prime[i] == 0) //如果n是某一个素数的倍数
        {
            n /= prime[i];
            a[i][id] ^= 1;  //a[i][j] i为第几个素数，j为第几个样例 ，a[i][j]为第j个数含有多少个第i个素数，如果含有偶数个素数，则结果为0，否则为1
            //所以求解异或方程组自由变元的个数cnt，每个自由变元可取的值为0或1，所以答案为这些自由变元的组合，即2^cnt-1
        }
    }
}

ll Gauss(ll equ,ll var) //返回自由变元个数，equ为行数（素数的个数），var为列数（输入元素的个数，也就是n)
{
    //初始化：将解都设为0，标记都不是自由变元
    for(ll i=0;i<=var;i++)
    {
        x[i]=0;
        freeX[i]=0;
    }

    /*转换为阶梯阵*/
    ll col=0; //当前处理的列
    ll row;   //当前处理的行
    ll num=0; //自由变元的序号
    for(row=0; row<equ && col<var ; row++,col++) //枚举当前处理的行
    {
        ll maxRow = row; //当前列绝对值最大的行

        for(ll i=row+1;i<equ;i++) //寻找当前列绝对值最大的行
        {
            if(abs(a[i][col])>abs(a[maxRow][col])) maxRow=i;
        }

        if(maxRow!=row) //与第row行交换
        {
            for(ll j=row;j<var+1;j++)
            {
                swap(a[row][j],a[maxRow][j]);
            }
        }

        if(a[row][col]==0) //即当前这一列全是0，处理当前行的下一列
        {
            freeX[num++]=col;//记录自由变元
            row--;//在for循环里面row要++，因为处理当前行的下一列，行数不用变，只要变列数就可以了，所以row要--，抵消掉for循环里面的++
            continue;
        }

        for(ll i=row+1;i<equ;i++) //从该行的下一行一直到最后一行
        {
            if(a[i][col]!=0)
            {
                for(ll j=col;j<var;j++) //对于下面出现该列中有1的行，需要把1消掉
                {
                    a[i][j]^=a[row][j];
                }
            }
        }
    }

    /*求解*/

    //无解：化简的增广阵中存在(0,0,...,a)这样的行，且a!=0
    //因为n<303，即列数<行数，所以最后row的位置肯定是最后一列，但是不到最后一行，根据上面的for循环，从row行开始，一直到最后一行，前col-1列每个都是0，但是最后一列（col列）不一定都是0，如果有不是0的（就是1），那么无解。
    for(ll i=row;i<equ;i++) //从第row行开始，一直到最后一行，如果最后一列的元素!=0，则无解，直接返回-1
    {
        if(a[i][col]!=0)
        {
            return -1;
        }
    }

    //无穷解: 在var*(var+1)的增广阵中出现(0,0,...,0)这样的行（即n*(n+1)中出现某一行全是0这样的行)
    ll temp=var-row; //因为如果有自由变元，则只有列变化，行数是不变化的，所以最后的自由变元有n-row个
    if(row<var) //返回自由变元数
    {
         return temp;
    }


    //唯一解: 在var*(var+1)的增广阵中形成严格的上三角阵
    for(ll i=var-1;i>=0;i--) //计算解集，这道题可以不用计算解集，可以不用写
    {
        x[i]=a[i][var];
        for(ll j=i+1;j<var;j++)
        {
            x[i]^=(a[i][j]&&x[j]);
        }
    }
    //如果形成唯一解，最后返回的结果就是0，2^0-1=0
    return 0;
}

ll enumFreeX(ll freeNum,ll var) //枚举自由元，统计有解情况下1最少的个数 ，这道题这里也可以不用写
{
    ll sta=(1<<(freeNum));//自由元的状态总数
    ll res=inf;
    for(ll i=0;i<sta;++i){//枚举状态
        ll cnt=0;
        for(ll j=0;j<freeNum;j++){//枚举自由元
            if(i&(1<<j)){
                cnt++;
                x[freeX[j]]=1;
            }else
                x[freeX[j]]=0;
        }
        for(ll k=var-freeNum-1;k>=0;k--){//没有自由元的最下面一行
            ll index=0;
            for(index=k;k<var;index++){//在当前行找到第一个非0自由元
                if(a[k][index])
                    break;
            }
            x[index]=a[k][var];
            for(ll j=index+1;j<var;++j){//向后依次计算出结果
                if(a[k][j])
                    x[index]^=x[j];
            }
            cnt+=x[index];//若结果为1，则进行统计
        }
        res=min(res,cnt);
    }
    return res;
}

ll qpow(ll a, ll b) //快速幂
{
    ll ans = 1;
    while(b) {
        if(b & 1)
            ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans % mod;
}

int main()
{
    init(); //初始化，将素数放入prime数组里面，从prime[0]开始存
    ll t, n; //给的数不超过300（n<=300)
    ll tmp;
    cin >> t; //一共几组样例
    for (int I=1;I<=t;I++)
    {
        cin >> n; //给出几个数
        memset(a, 0, sizeof(a));   //a是增广矩阵
        for(ll i = 0; i < n; ++i)
        {
            cin >> tmp;
            solve(i, tmp);
        }
        ll freeNum = Gauss(tot,n); //用高斯消元求解异或方程组（解出自由元个数） (tot为素数的个数，n为一共输入多少个数)
        printf("Case #%d:\n%lld\n",  I , (qpow(2, freeNum) - 1 + mod) % mod); //最后的结果为2^cnt(自由变元个数)-1
    }
    return 0;
}