高斯消元/异或方程组-HDU 5833-Zhu and 772002

曾经终败给现在 2022-05-15 11:36 180阅读 0赞

*  # 高斯消元/异或方程组-HDU 5833-Zhu and 772002 #

--------------------

*  ## 题目链接： ##

### [Zhu and 772002][] ###

*  ## 题目基础： ##

### [高斯消元法(含异或方程组求解）][Link 1] ###

*  ## 思路: ##

### 题目大意： ###

给N个数，选出1~k个数相乘，问有多少种方式，使得相乘结果为完全平方数

### 题解： ###

**完全平方数可由素数因子相乘而得，并且每种因子成对存在**

题目给了一个重要提示，素数因子不会大于2000，不妨将N个数分解成素数因子相乘，用Xi 表示第 i 个数是否选择，0选 1不选

![Center][]

*  ## 代码： ##

#include<bits/stdc++.h>
    using namespace std;
    #define MAX_SIZE 350
    #define Mod 1000000007
    #define ll long long
    ll Matrix[MAX_SIZE][MAX_SIZE];
    ll Free_x[MAX_SIZE];   //自由变元
    ll X_Ans[MAX_SIZE];  //解集
    ll Data[MAX_SIZE];
    ll Free_num=0;  //自由变元数
    
    ll Guass(ll Row,ll Column)  //系数矩阵的行和列
    {
        ll row=0,col=0,max_r;
        for(row=0;row<Row&&col<Column;row++,col++)
        {
            max_r=row;
            for(ll i=row+1;i<Row;i++)   //找出当前列最大值
                if(abs(Matrix[i][col])>abs(Matrix[max_r][col]))
                    max_r=i;
            if(Matrix[max_r][col]==0)  //记录自由变元
            {
                row--;
                Free_x[Free_num++]=col+1;
                continue;
            }
            if(max_r!=row)  //交换
                for(ll i=col;i<Column+1;i++)
                    swap(Matrix[row][i],Matrix[max_r][i]);
            for(ll i=row+1;i<Row;i++)   //消元
            {
                if(Matrix[i][col]!=0)
                {
                    for(ll j=col;j<Column+1;j++)
                        Matrix[i][j]^=Matrix[row][j];
                }
            }
        }
        for(ll i=row;i<Row;i++)   //无解
            if(Matrix[i][Column]!=0)
                return -1;
    
        if(row<Column)   //无穷多解
            return Column-row;
    
        //唯一解
        for(ll i=Column-1;i>=0;i--)
        {
            X_Ans[i]=Matrix[i][Column];
            for(ll j=i+1;j<Column;j++)
               X_Ans[i]^=(Matrix[i][j]&&X_Ans[j]);
        }
        return 0;
    }
    
    const int MAXN = 2200;
    ll prime[MAXN+1];
    void getPrime()  //素数筛
    {
        memset(prime,0,sizeof(prime));
        for(int i = 2; i <= MAXN; i++)
        {
            if(!prime[i])prime[++prime[0]] = i;
            for(int j = 1; j <= prime[0] && prime[j] <= MAXN/i; j++)
            {
                prime[prime[j]*i] = 1;
                if(i%prime[j] == 0)break;
            }
        }
    }
    
    ll quick_mod(ll a,ll b)  //快速幂
    {
        ll ans=1;
        while(b)
        {
            if(b&1)
            {
                ans=(ans*a)%Mod;
                b--;
            }
            b/=2;
            a=a*a%Mod;
        }
        return ans;
    }
    
    
    int main()
    {
        getPrime();
        int T,m;
        int Case_num=1;
        cin>>T;
        while(T--)
        {
            Free_num=0;
            cin>>m;
            for(int i=0;i<m;i++)
                scanf("%lld",&Data[i]);
            ll t=303;
            ll Column=m;
            ll Row=t;
            for(int i=0;i<t;i++)
                for(int j=0;j<m;j++)
                {
                    int cnt=0;
                    while(Data[j]%prime[i+1]==0)
                    {
                        cnt++;
                        Data[j]/=prime[i+1];
                    }
                    Matrix[i][j]=(cnt&1);
                }
            for(int i=0;i<t;i++)
                Matrix[i][m]=0;
            ll flag=Guass(Row,Column);
            ll ans=quick_mod(2,Free_num);
            ans=(ans-1)%Mod;
            cout<<"Case #"<<Case_num++<<":"<<endl;
            cout<<ans<<endl;
        }
        return 0;
    }

*  ## 参考： ##

### 而濡木染-[hdu5833 Zhu and 772002 （高斯消元的简单应用）][hdu5833 Zhu and 772002] ###

[Zhu and 772002]: http://acm.hdu.edu.cn/showproblem.php?pid=5833
[Link 1]: https://blog.csdn.net/SZU_Crayon/article/details/82155056
[Center]: /images/20220515/f4e73f2c580e418b8d46cac61e409562.png
[hdu5833 Zhu and 772002]: https://blog.csdn.net/PNAN222/article/details/52209980