Light OJ 1288 Subsets Forming Perfect Squares 高斯消元求矩阵的秩

题目来源：Light OJ 1288 Subsets Forming Perfect Squares

题意：给你n个数选出一些数他们的乘积是全然平方数求有多少种方案

思路：每一个数分解因子每隔数能够选也能够不选 0 1表示然后设有m种素数因子选出的数组成的各个因子的数量必须是偶数

组成一个m行和n列的矩阵每一行代表每一种因子的系数解出*元的数量

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

const int maxn = 1010;

const int mod = 1000000007;

typedef int Matrix[maxn][maxn];

typedef long long LL;

int prime[maxn];

bool vis[maxn];

//返回a^p mod n 高速幂

LL pow_mod(LL a, LL p, LL n)

{

	LL ans = 1;

	while(p)

	{

		if(p&1)

		{

			ans *= a;

			ans %= n;

		}

		a *= a;

		a %= n;

		p >>= 1;

	}

	return ans;

}

void sieve(int n)

{

	int m = sqrt(n+0.5);

	memset(vis, 0, sizeof(vis));

	vis[0] = vis[1] = 1;

	for(int i = 2; i <= m; i++)

		if(!vis[i])

			for(int j = i*i; j <= n; j += i)

				vis[j] = 1;

}

int get_primes(int n)

{

	sieve(n);

	int c = 0;

	for(int i = 2; i <= n; i++)

		if(!vis[i])

			prime[c++] = i;

	return c;

}

int rank(Matrix A, int m, int 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()

{

	int cas = 1;

	int m = get_primes(500);

	int T;

	scanf("%d", &T);

	while(T--)

	{

		int n, maxp = 0;

		scanf("%d", &n);

		memset(A, 0, sizeof(A));

		for(int i = 0; i < n; i++)

		{

			long long x;

			scanf("%lld", &x);

			for(int j = 0; j < m; j++)

			{

				while(x % prime[j] == 0)

				{

					maxp = max(maxp, j);

					x /= prime[j];

					A[j][i] ^= 1;

				}

			}

		}

		int r = rank(A, maxp+1, n);

		printf("Case %d: %lld\n", cas++, pow_mod(2, n-r, mod)-1);

	}

	return 0;

}