描述

两个数a和 b (a<b)被称为质数相关，是指a × p = b，这里p是一个质数。一个集合S被称为质数相关，是指S中存在两个质数相关的数，否则称S为质数无关。如{2, 8, 17}质数无关，但{2, 8, 16}, {3, 6}质数相关。现在给定一个集合S，问S的所有质数无关子集中，最大的子集的大小。

输入

第一行为一个数T，为数据组数。之后每组数据包含两行。

第一行为N，为集合S的大小。第二行为N个整数，表示集合内的数。

输出

对于每组数据输出一行，形如"Case #X: Y"。X为数据编号，从1开始，Y为最大的子集的大小。

数据范围

1 ≤ T ≤ 20

集合S内的数两两不同且范围在1到500000之间。

小数据

1 ≤ N ≤ 15

大数据

1 ≤ N ≤ 1000

 #include <bits/stdc++.h>

 using namespace std;

 int T, N;

 vector<int> v;

 vector<vector<int>> graph;

 vector<int> link;

 vector<bool> visited;

 bool *isPrime;

 void getPrime() {

     isPrime = new bool[];

     memset(isPrime, true, sizeof(bool) * );

     isPrime[] = isPrime[] = false;

     for (int i = ; i * i < ; ++i) if (isPrime[i]) {

         for (int j = ; i * j < ; ++j) isPrime[i * j] = false;

     }

 }

 int dfs(int u) {

     for (auto v : graph[u]) if (!visited[v]) {

         visited[v] = true;

         if (link[v] == - || dfs(link[v])) {

             link[v] = u;

             return ;

         }

     }

     return ;

 }

 int hungary() {

     int res = ;

     for (int i = ; i < N; ++i) {

         visited.assign(N + , false);

         res += dfs(i);

     }

     return res / ;

 }

 int main() {

     getPrime();

     cin >> T;

     for (int t = ; t <= T; ++t) {

         cin >> N;

         v.resize(N);

         for (int i = ; i < N; ++i) {

             cin >> v[i];

         }

         sort(v.begin(), v.end());

         graph.assign(N + , vector<int>());

         link.assign(N + , -);

         for (int i = ; i < N - ; ++i) {

             for (int j = i + ; j < N; ++j) {

                 if (v[j] % v[i] == ) {

                     int tmp = v[j] / v[i];

                     if (isPrime[tmp]) {

                         graph[i].push_back(j);

                         graph[j].push_back(i);

                     }

                 }

             }

         }

         cout << "Case #" << t << ": ";

         int res = hungary();

         cout << N - res << endl;

     }

     return ;

 }