题目链接：点击打开链接

白书的例题练练手。

。

。

P161

#include <cstdio>

#include <iostream>

#include <algorithm>

#include <math.h>

#include <string.h>

#include <algorithm>

using namespace std;

#define ll int

#define LL long long

const int mod = 1000000009;

const int maxn = 510;

const int maxp = 100;

ll prime[1000],primenum;//有primenum个素数 math.h

void PRIME(ll Max_Prime){

	primenum=0;

	prime[primenum++]=2;

	for(ll i=3;i<=Max_Prime;i+=2)

	for(ll j=0;j<primenum;j++)

		if(i%prime[j]==0)break;

		else if(prime[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 <<endl;

    }

    return 0;

}