解題區/解題區 - UVa

UVa 11542 - Square

contents

  1. 1. Input
  2. 2. Output
  3. 3. Sample Input
  4. 4. Output for Sample Input
  5. 5. Solution

Given n integers you can generate $2^{n} - 1$ non-empty subsets from them. Determine for how many of these subsets the product of all the integers in that is a perfect square. For example for the set {4,6,10,15} there are 3 such subsets. {4}, {6,10,15} and {4,6,10,15}. A perfect square is an integer whose square root is an integer. For example 1, 4, 9, 16,…. .

Input

Input contains multiple test cases. First line of the input contains T(1≤T≤30) the number of test cases. Each test case consists of 2 lines. First line contains n(1≤n≤100) and second line contains n space separated integers. All these integers are between 1 and 10^15. None of these integers is divisible by a prime greater than 500.

Output

For each test case output is a single line containing one integer denoting the number of non-empty subsets whose integer product is a perfect square. The input will be such that the result will always fit into signed 64 bit integer.

Sample Input

1
2
3
4
5
6
7
8
9
4
3
2 3 5
3
6 10 15
4
4 6 10 15
3
2 2 2

Output for Sample Input

1
2
3
4
0
1
3
3

Solution

題目描述：

將 N 個數字，任挑相乘為平方數的方法數有多少？

題目解法：

將每個數字做質因數分解，對於每個質數將會有一條方程式，其參數為能貢獻的質因數的個數。

x1 = 0 表示第一個數字如果不選，x1 = 1 則表示選。

因此，最後希望所有方程式加總都必須要是偶數。

$$a_{1}x_{1} + a_{2}x_{2} + ... = even \quad for \quad prime \quad 2 \\ b_{1}x_{1} + b_{2}x_{2} + ... = even \quad for \quad prime \quad 3 \\ ...$$

使用 XOR 高斯消去法，找到任意解的變數個數 (大陸: 自由基) 即能得到所有解個數大小。

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
#include <stdio.h> 
#include <algorithm>
using namespace std;
#define maxL (500>>5)+1
#define GET(x) (mark[x>>5]>>(x&31)&1)
#define SET(x) (mark[x>>5] |= 1<<(x&31))
int mark[maxL];
int P[505], Pt = 0;
void sieve() {
    register int i, j, k;
    SET(1);
    int n = 500;
    for(i = 2; i <= n; i++) {
        if(!GET(i)) {
            for(k = n/i, j = i*k; k >= i; k--, j -= i)
                SET(j);
            P[Pt++] = i; 
        }
    }
}
int main() {
    sieve();
    int testcase, n;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d", &n);
        
        int f[505][505] = {};
        long long x;
        for(int i = 0; i < n; i++) {
            scanf("%lld", &x);
            for(int j = 0; j < Pt; j++)
                while(x%P[j] == 0)
                    x /= P[j], f[j][i] ^= 1;
        }
        // xor gauss
        int row = Pt, col = n, arb = 0;
        for(int r = 0, c = 0; r < row && c < col; c++) {
            int k = r;
            for(int j = r + 1; j < row; j++)
                if(f[j][c])	k = j;
            for(int j = 0; j < col; j++)
                swap(f[r][j], f[k][j]);
                
            if(f[r][c] == 0) {arb++;continue;}
            
            for(int j = 0; j < row; j++) {
                if(r == j)	continue;
                if(f[j][c]) {
                    for(int k = col; k >= c; k--)
                        f[j][k] = f[j][k] ^ f[r][k];
                }
            }
            r++;
        }
        printf("%lld\n", (1LL<<arb) - 1);
    }
    return 0;
}