UVA 11542 Square 高斯消元异或方程组求解-白红宇

UVA 11542 Square 高斯消元异或方程组求解

阅读量：7092 次

发布时间：2019-06-28

本文共 1196 字，大约阅读时间需要 3 分钟。

题目链接：

白书的例题练练手。

。

P161

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;#define ll int#define LL long longconst int mod = 1000000009;const int maxn = 510;const int maxp = 100;ll prime[1000],primenum;//有primenum个素数 math.hvoid PRIME(ll Max_Prime){ primenum=0; prime[primenum++]=2; for(ll i=3;i<=Max_Prime;i+=2) for(ll j=0;j
           
            sqrt((double)i) || j==primenum-1) { prime[primenum++]=i; break; }}typedef int Matrix[maxn][maxn];int rank(Matrix A, int m, int n) { //m个方程n个变量 int i = 0, j = 0, k, r, u; while(i < m && j < n) { r = i; for(k = i; k < m; k++) if(A[k][j]) { r = k; break; } if(A[r][j]) { if(r != i) for(k = 0; k <= n; k++) swap(A[r][k], A[i][k]); for(u = i+1; u < m; u++) if(A[u][j]) for(k = i; k <= n; k++) A[u][k] ^= A[i][k]; i++; } j++; } return i;}Matrix A;int main(){ PRIME(500); int T; cin>>T; while(T--) { int n, maxp = 0; long long x; cin>> n; memset(A, 0, sizeof A); for(int i = 0; i < n; i++) { cin>> x; for(int j = 0; j < primenum; j++) while(x % prime[j] == 0) { maxp = max(maxp, j); x /= prime[j]; A[j][i] ^= 1; } } int r = rank(A, maxp+1, n); cout<< (1LL << (n-r))-1 <