Fork me on GitHub

[UVa-11542] Square

发表于 | 分类于
字数统计: 473字 | 阅读时长 ≈ 3分钟

题面

传送门UVa-11542
题目大意:给出一个整数集合从中挑出至少一个使得积为完全平方数。

样例

Sample Input
4
3
2 3 5
3
6 10 15
4
4 6 10 15
3
2 2 2
Sample Output
0
1
3
3

思路

高斯消元+xor矩阵
先处理出前面500的质数
写成m个异或的方程 自上而下求解即可
异或的话可以用bitset优化但是，，我不会用啊

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include<bits/stdc++.h>
using namespace std;
const int maxn = 510;
const int maxp = 100;
typedef int Matrix[maxn][maxn];
bool is_prime[maxn];
int prime[maxp],cnt=0;
inline void read(int &x)
{
	x=0;char ch=getchar();int f=1;
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
	x*=f;
}

void Euler_Prime(int s)
{
	memset(is_prime,1,sizeof(is_prime));
	is_prime[1] = 0; //1 不是质数. 
	for (int i = 2; i <= s; i++)
	{
		if (is_prime[i]) prime[cnt++] = i;
		for (int j = 0; j < cnt && i * prime[j] <= s; j++)
		{
			is_prime[prime[j] * i] = 0;
			if (i % prime[j] == 0) break;
		}
	}
}
Matrix A;
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;
}
int main(int argc, char *argv[]) 
{
  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 < cnt; j++)
        while(x % prime[j] == 0) 
		{
          maxp = max(maxp, j); x /= prime[j]; A[j][i] ^= 1;
        }
    }
    int r = rank(A, maxp+1, n); // 只用到了前maxp+1个素数
    cout << (1LL << (n-r))-1 << endl;
  }
  return 0;
}