HDU - 5833 Zhu and 772002（异或方程组）

传送门：HDU - 5833

思路分析

由于质数最大只有2000，所以我们可以将每个数质因数分解，能够组成完全平方数，那么它的每个质因子都是偶数次，模2意义下的方程组就是异或方程组，那么解的个数就是$2^{自由元个数} - 1$

AC代码

#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define fun function
#define sz(x) (int)(x).size()
#define lowbit(x) (x)&(-x)
#define all(x) (x).begin(),(x).end()
#define mem(a,b) memset(a,b,sizeof(a))

namespace FastIO {
#define BUF_SIZE 100000
#define OUT_SIZE 100000
    bool IOerror=0;
    inline char nc() {
        static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE;
        if(p1==pend) {
            p1=buf;
            pend=buf+fread(buf,1,BUF_SIZE,stdin);
            if(pend==p1) {
                IOerror=1;
                return -1;
            }
        }
        return *p1++;
    }
    inline bool blank(char ch) {
        return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';
    }
    template<class T> inline bool read(T &x) {
        bool sign=0;
        char ch=nc();
        x=0;
        for(; blank(ch); ch=nc());
        if(IOerror)return false;
        if(ch=='-')sign=1,ch=nc();
        for(; ch>='0'&&ch<='9'; ch=nc())x=x*10+ch-'0';
        if(sign)x=-x;
        return true;
    }
    template<class t> inline void print(t x) {
        if (x < 0) putchar('-'), print(-x);
        else {
            if (x > 9) print(x / 10);
            putchar('0' + x % 10);
        }
    }
    template<class T,class... U>bool read(T& h,U&... t) {
        return read(h)&&read(t...);
    }
#undef OUT_SIZE
#undef BUF_SIZE
};
using namespace std;
using namespace FastIO;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define int long long
typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;

const int INF = 0x3f3f3f3f;
const int N = 303;
const int mod = 1e9+7;

ll qpow(ll x, int n) {
    ll res = 1;
    while(n) {
        if(n&1) res = res * x % mod;
        x = x * x % mod;
        n /= 2;
    }
    return res;
}
  

bitset<N>a[N];//增广矩阵
int x[N];//解集
int freeX[N];//自由变元
int Gauss(int equ, int var) //返回自由变元个数,equ行，var列 
{
    /*初始化*/
    for (int i = 0; i <= var; i++) {
        x[i] = 0;
        freeX[i] = 0;
    }
    /*转换为阶梯阵*/
    int col = 0;//当前处理的列
    int num = 0;//自由变元的序号
    int row;//当前处理的行
    for (row = 0; row < equ && col < var; row++, col++) {//枚举当前处理的行
        int maxRow = row;//当前列绝对值最大的行
        for (int i = row + 1; i < equ; i++) {//寻找当前列绝对值最大的行
            if (abs(a[i][col]) > abs(a[maxRow][col]))
                maxRow = i;
        }
        if (maxRow != row) {//与第row行交换
            swap(a[row],a[maxRow]);
        }
        if (a[row][col] == 0) {//col列第row行以下全是0，处理当前行的下一列
            freeX[num++] = col;//记录自由变元
            row--;
            continue;
        }
 
        for (int i = row + 1; i < equ; i++) {
            if (a[i][col] != 0) {
                a[i]^=a[row];
            }
        }
    }
 
    /*求解*/
    //无解：化简的增广阵中存在(0,0,...,a)这样的行，且a!=0
    for (int i = row; i < equ; i++)
        if (a[i][col] != 0)
            return -1;
 
    //无穷解: 在var*(var+1)的增广阵中出现(0,0,...,0)这样的行
    int temp = var - row;//自由变元有var-row个
    if (row < var)//返回自由变元数
        return temp;
 
    //唯一解: 在var*(var+1)的增广阵中形成严格的上三角阵
    for (int i = var - 1; i >= 0; i--) {//计算解集
        x[i] = a[i][var];
        for (int j = i + 1; j < var; j++)
            x[i] ^= (a[i][j] && x[j]);
    }
    return 0;
}

int prim[2010],cnt,isprim[2010];

void getprim(int maxn){
    for(int i=2;i<=maxn;i++){
        if(!isprim[i]) {
            isprim[i] = 1;
            prim[cnt++] = i;
        }
        for(int j = i*i;j<=maxn;j+=i) isprim[j] = 1;
    }
}


signed main() {

#ifdef xiaofan
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif

    getprim(2010);
    int T;
    read(T);
    for(int _=1;_<=T;_++){
        int n;
        for(int i=0;i<N;i++) a[i].reset();
        read(n);
        int m = 0;
        for(int i=0;i<n;i++){
            int x;
            read(x);
            for(int j=0;j<cnt;j++){
                if(x%prim[j] == 0){
                    int sum = 0;
                    while(x%prim[j] == 0) {
                        sum++;
                        x/=prim[j];
                    }
                    if(sum&1) a[j][i] = 1;
                    m = max(m,j);
                }
            }
        }
        int ans = Gauss(m+1,n);
        ans = qpow(2,ans)%mod;
        ans = (ans-1+mod)%mod;
        printf("Case #%lld:\n%lld\n",_,ans);
    }





    return 0;
}
/*
55
6
23 878 23 11 22 31
*/