题目大意

题目链接

A set of integers is called prime independent if none of its member is a prime multiple of another member. An integer a is said to be a prime multiple of b if,

a = b x k (where k is a prime [1])

So, 6 is a prime multiple of 2, but 8 is not. And for example, {2, 8, 17} is prime independent but {2, 8, 16} or {3, 6} are not.

Now, given a set of distinct positive integers, calculate the largest prime independent subset.

Input

Input starts with an integer T (≤ 20), denoting the number of test cases.

Each case starts with an integer N (1 ≤ N ≤ 40000) denoting the size of the set. Next line contains N integers separated by a single space. Each of these N integers are distinct and between 1 and 500000 inclusive.

Output

For each case, print the case number and the size of the largest prime independent subset.

Sample Input

1
2
3
4
5
6
7
3
5
2 4 8 16 32
5
2 3 4 6 9
3
1 2 3

Sample Output

1
2
3
Case 1: 3
Case 2: 3
Case 3: 2

分析

题意 ： 找出一个集合中的最大独立集，任意两数字之间不能是素数倍数的关系。
这题最关键是如何建边 ： 如果这两个数是素数倍数关系， 那么这两个数的质因数的个数肯定一个是奇数个， 一个是偶数个， 这么建边。

AC代码

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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include <bits/stdc++.h>

using namespace std;
#define ms(a, b) memset((a), (b), sizeof(a))

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
const int N = 4e4 + 5;
const int M = 5e5 + 5;
const int INF = 0x3f3f3f3f;
const ll ll_max = 4557430888798830399;
inline int read() {
    int res = 0;bool f = 0;char ch = getchar();
    while (ch < '0' || ch > '9')  {if (ch == '-') f = 1;ch = getchar();}
    while (ch <= '9' && ch >= '0') {res = (res << 3) + (res << 1) + ch - '0';ch = getchar();}
    return f ? (~ res + 1) : res;
}
int vis[N];
int match[N];
vector<int>fac[N];
int pos[M];
int cnt[N];
struct edge {
    int u, v, ne;
} ed[M];

int head[M], cnt1;
int a[N], n;
int pri[M];
bool is[M];
int num = 0;

void is_pri(int n){
	ms(is, true);
	is[1] = is[0] = false;
	for (int i = 2; i <= n; ++i){
		if (is[i]) pri[++num] = i;
		for (int j = 1; j <= num && i * pri[j] <= n; ++j){
			is[i * pri[j]] = false;
			if (i % pri[j] == 0) break;
		}
	}
}

inline void add(int u, int v) {
    ed[cnt1] = {u, v, head[u]};
    head[u] = cnt1++;
}

int tofind(int u, int sgn) { // 二分图匹配
    for (int i = head[u]; ~i; i = ed[i].ne) {
        int v = ed[i].v;
        // if (match[u]) continue;
        if (vis[v] != sgn) { 
            vis[v] = sgn;
            if (!match[v] || tofind(match[v], sgn)) {
                match[v] = u;
                // match[u] = v;
                return 1;
            }
        }

    }
    return 0;
}

int main() {
    int t;
    is_pri(500000);
    // cout << num << "\n";
    t = read();
    for (int tt = 1; tt <= t; ++tt) {
        n = read();
        ms(head, -1);
        for (int i = 1; i <= n; ++i) {
            int tmp;
            tmp = a[i] = read();
            // ↓ 分解质因数
            pos[tmp] = i;
            for (int p = 1; p <= num && pri[p] * pri[p] <= tmp; ++p) {
                if (tmp % pri[p] == 0) {
                    fac[i].push_back(pri[p]);
                    while(tmp % pri[p] == 0) tmp /= pri[p], ++cnt[i];
                }
            }
            if (tmp > 1) fac[i].push_back(tmp), ++cnt[i];
        }

        for (int i = 1; i <= n; ++i) {
            int L = fac[i].size();
            for (int j = 0; j < L; ++j) {
                int k = pos[a[i] / fac[i][j]]; // 如果存在这个数的话
                if (k) {
                    if (cnt[i] & 1) add(i, k); // 如果i的质因子的个数是奇数个
                    else add(k, i);  // 否则k的质因子个数为奇数个
                }
            }

        }
        int ans = 0;
        for (int i = 1; i <= n; ++i) {
            if (tofind(i, i)) ans += 1;
        }
        printf("Case %d: %d\n", tt, n - ans);
        for (int i = 1; i <= n; ++i) {
            pos[a[i]] = 0;
            vis[i] = cnt[i] = pos[i] = match[i] = cnt1 = 0;
            fac[i].clear();

        }
    }

    return 0;
}
1
恰似你一低头的温柔，娇弱水莲花不胜寒风的娇羞， 我的心为你悸动不休。  --mingfuyan