HDU 5833 题解：基于高斯消元的异或空间计数

HDU 5833 题解

问题描述

给定 n 个数 a1, a2, ..., an，每个数的质因子均不超过 2000。要求从中选出至少一个数相乘，使得得到的积 b 是一个完全平方数。求不同的选择方案数，结果对 1000000007 取模。

解题思路

一个数是完全平方数，当且仅当其所有质因子的指数均为偶数。因此，我们可以将每个数表示为一个向量，向量的第 i 位表示第 i 个质因子的指数奇偶性（0 为偶，1 为奇）。

问题转化为寻找一组向量，其异或和为全零向量。这实际上是在求线性空间的基的维数。设自由变量个数为 k，则总方案数为 2^k - 1（减去空集）。

我们需要构建一个增广矩阵，行对应质数，列对应输入的数。如果第 j 个数的第 i 个质因子指数为奇数，则矩阵中 (i, j) 位置为 1，否则为 0。最后通过高斯消元法在模 2 意义下求解。

代码实现

#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<string.h>
#include<math.h>
using namespace std;
typedef long long int ll;
const int MAXN=305;
const int MOD = 1e9+7;
int a[MAXN][MAXN]; // 增广矩阵
int x[MAXN];       // 解集
bool free_x[MAXN]; // 标记是否是不确定的变元

inline int gcd(int a,int b)
{
    int t;
    while(b!=0)
    {
        t=b; b=a%b; a=t;
    }
     a;
}



{
     i,j,k;
     max_r,col,ta,tb,LCM,temp,free_x_num,free_index;
    ( i=;i<=var;i++) { x[i]=; free_x[i]=; }
    
    col=;
    (k = ;k < equ && col < var;k++,col++)
    {
        max_r=k;
        (i=k;i<equ;i++)
        {
            ((a[i][col])>(a[max_r][col])) max_r=i;
        }
        (max_r!=k)
        {
            (j=k;j<var;j++) (a[k][j],a[max_r][j]);
        }
        (a[k][col]==)
        {
            k--; ;
        }
        (i=k;i<equ;i++)
        {
            (a[i][col]!=)
            {
                
                
                LCM = ((a[i][col]),(a[k][col]));
                ta = LCM/(a[i][col]);
                tb = LCM/(a[k][col]);
                (a[i][col]*a[k][col]<)tb=-tb;
                (j=col;j<var;j++)
                {
                    a[i][j] = (MOD + (a[i][j]%MOD)*ta - (a[k][j]%MOD)*tb)%MOD;
                }
            }
        }
    }
    
    
     (i = k; i < equ; i++)
    {
         ( (a[i][col]%MOD) != )  ;
    }
    
     (k < var)
    {
         var - k; 
    }
    
    
     (i = var - ; i >= ; i--)
    {
        temp = a[i][var];
         (j = i + ; j < var; j++)
        {
             (a[i][j] != ) temp -= a[i][j] * x[j];
        }
         (temp % a[i][i] != )  ;
        x[i] = temp / a[i][i];
    }
     ;
}

 prime[];
 spring[];
 count_prime = ;

{
    ( i=; i<=; i++)
    {
        (spring[i]==)
        {
            prime[count_prime++] = i;
            ( j=*i; j<=; j+=i) spring[j] = ;
        }
    }
}

{
    ll ans = ;
    ( m )
    {
        ( m% ) ans = (ans*a)%MOD;
        a = (a*a)%MOD;
        m /= ;
    }
     ans;
}

{
    ();
     T;
    (,&T);
     N;
     Case = ;
    ll num;
     Count;
    (T--)
    {
        (,&N);
        ( i=; i<N; i++)
        {
            (,&num);
            ( j=; j<count_prime; j++)
            {
                Count = ;
                ( num && num%prime[j]== )
                {
                    Count++;
                    num /= prime[j];
                }
                a[j][i] = Count%;
            }
        }
        ( i=; i<count_prime; i++) a[i][N] = ;
        
         ans = (count_prime,N);
        (ans<=)
        {
            (,++Case);
            ();
        }
        
        {
            (,++Case);
            ll ANS = ((ll),(ll)ans);
            ANS--;
            (,( )(ANS+MOD)%MOD);
        }
    }
     ;
}