推荐两个博客：
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;
}
投递建信金科等公司10个岗位 >