传送门

---

题目大意

给出一个序列，选出一个最大的集合，使得这个集合中的任意两个数，都不存在素数倍关系。一对数$x,y$有素数倍关系，即$x=p\ast y(y=p\ast x)$。

解题思路

两个数有素数倍关系，那么这个质数$p$有很多取值的可能，而且即使找到给出序列中所有的关系，正常思路也无从下手…

使用二分图去求解这样的给定限制的集合，这个思路真的很神奇。为什么能构成二分图——从质因数的奇偶性下手！不难知道一个数如果乘上一个素数后，那么它的质因数个数的奇偶性一定发生变化。这样，我们将初始质因数个数为奇数的数放在左边点集，偶数放在右边点集。建图时，枚举每个数的质因数，看看它除以每种质因子后的结果是否出现在序列中，如果出现一定在另外一边的点集，连边即可。注意：$1$是特殊的，因为它乘上一个素数后质因数个数变成了奇数，但是它又没有任何质因子，需要放在偶数点集中

点最多有$4e4$个，匈牙利算法已经无法求解了，需要使用$HK$算法或者最大流的$Dinic$算法。下面的$HK$算法参考了红书模板。

这题内存卡的贼紧，无语，一开始想着尽可能降低时间复杂度，结果后面要时间换空间？！

//
// Created by Happig on 2020/11/14
//
#include <bits/stdc++.h>
#include <unordered_map>using namespace std;
#define fi first
#define se second
#define pb push_back
#define ins insert
#define Vector Point
#define ENDL "\n"
#define lowbit(x) (x&(-x))
#define mkp(x, y) make_pair(x,y)
#define mem(a, x) memset(a,x,sizeof a);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
const double eps = 1e-8;
const double pi = acos(-1.0);
const int inf = 0x3f3f3f3f;
const double dinf = 1e300;
const ll INF = 1e18;
const int Mod = 1e9 + 7;
const int maxn = 5e5 + 10;
const int maxm = 4e4 + 10;vector<int> fac[maxn];void divide(int n) {int m = n, num = 0;for (int i = 2; i * i <= m; i++) {if (n % i == 0) {fac[m].push_back(i);while (n % i == 0) ++num, n /= i;}if (n == 1) break;}if (n > 1) ++num, fac[m].push_back(n);fac[m].push_back(num);
}vector<int> even, odd;
bitset<maxn> exist;
int idx[maxn];int n1, n2;
int mx[maxm], my[maxm], dx[maxm], dy[maxm];
queue<int> q;
bitset<maxm> vis;
vector<int> g[maxm];bool find(int u) {for (int i = 0; i < g[u].size(); i++) {int v = g[u][i];if (!vis[v] && dy[v] == dx[u] + 1) {vis[v] = 1;if (!my[v] || find(my[v])) {mx[u] = v, my[v] = u;return true;}}}return false;
}int matching() {memset(mx, 0, sizeof mx);memset(my, 0, sizeof my);int ans = 0;while (1) {bool ok = 0;while (!q.empty()) q.pop();memset(dx, 0, sizeof dx);memset(dy, 0, sizeof dy);for (int i = 1; i <= n1; i++) {if (!mx[i]) q.push(i);}while (!q.empty()) {int u = q.front();q.pop();for (int i = 0; i < g[u].size(); i++) {int v = g[u][i];if (!dy[v]) {dy[v] = dx[u] + 1;if (my[v]) {dx[my[v]] = dy[v] + 1;q.push(my[v]);} else ok = 1;}}}if (!ok) break;vis.reset();for (int i = 1; i <= n1; i++)if (!mx[i] && find(i)) ans++;}return ans;
}int main() {//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);int T, n, kase = 0;cin >> T;while (T--) {cin >> n;exist.reset();even.clear(), odd.clear();for (int i = 1, x; i <= n; i++) {cin >> x;if (!fac[x].size()) divide(x);exist[x] = 1, g[i].clear();if (x == 1) {even.push_back(x);continue;}if (fac[x].back() & 1) odd.push_back(x);else even.push_back(x);}n1 = even.size(), n2 = odd.size();int cur = 0;for (auto u:even) idx[u] = ++cur;for (auto u:odd) idx[u] = ++cur;for (auto u:even) {if (u == 1) continue;for (int i = 0; i < fac[u].size() - 1; i++) {int p = fac[u][i];if (exist[u / p]) {//cout << u << " " << u / p << endl;g[idx[u]].push_back(idx[u / p]);}}}for (auto u:odd) {for (int i = 0; i < fac[u].size() - 1; i++) {int p = fac[u][i];if (exist[u / p]) {//cout << u << " " << u / p << endl;g[idx[u / p]].push_back(idx[u]);}}}int res = matching();cout << "Case " << ++kase << ": " << n - res << ENDL;}return 0;
}