冒个泡(?
rainbow_sjy 老师做法.
gcd > 1 无论是 fair 还是 antifair 都无法给出一个很好的限制, 这启发我们建立补图, 即化为 gcd = 1, 此时两种判定分别是: 选出大小为 \(k\) 的独立集 和 选出大小为 \(k\) 且每个点所在联通块 \(\ge 2\).
考虑 \(2k\le n\) 的条件, 大概感觉一下是暗示我们, 在不满足第一个条件的情况下第二个条件必然满足, 那么我们找一个比较松的限制去判定, 所以以联通块为单位元来做.
第一个限制看起来比较困难, 我们先用一个比较松的条件: 如果联通块个数 \(\ge k\) 则有解, 构造显然, 判定也是简单的, 利用 mobius 反演每次加入一个数后看会不会和其他点连边即可.
尝试对于其它情况构造: 我们此时有 \(<k\) 个联通块，删除没有用的孤立点以后显然会剩下 \(p\ge \frac{n}{2}\ge k\) 个点, 我们从每个联通块选 \(\ge 2\) 个点即可.
于是我们现在需要知道每个联通块的具体情况, 我是不会这个的, sjy 老师给了一个高妙的解法, 直接整体二分, 大概就是先把上面那些独立集的点当作联通块的根, 对于点 \(x\), 若 \(x\) 和独立集 \([l,mid]\) 间的点有连边就向左递归, 反之向右递归, 于是得到了联通块的具体情况就可以直接做了. 时间复杂度 \(\mathcal O(n\log n2^{\omega(V)})\).
十分强大的题目和解法. 对于这类图上的构造, 积极地运用图上关系形式化描述判定条件方便思考, 对于其余题目, 描述二元组关系时也可以积极建图. 尽量将建图方式向提供便利限制地方向靠拢.
#include <bits/stdc++.h>
#define pb emplace_back
#define fir first
#define sec secondusing i64 = long long;
using pii = std::pair<int, int>;constexpr int maxn = 1e5 + 5, N = 1e7;
int prime[N + 5], cnt, mu[N + 5];
bool flag[N + 5];void init(int n) {mu[1] = 1;for(int i = 2;i <= n;++ i) {if(!flag[i]) prime[++ cnt] = i, mu[i] = -1;for(int j = 1;j <= cnt&&i * prime[j] <= n;++ j) {flag[i * prime[j]] = true;if(i % prime[j]) {mu[i * prime[j]] = -mu[i];} else {mu[i * prime[j]] = 0;break ;}}}return ;
}
int n, k, a[maxn], sum[N + 5], ord[maxn];
std::vector<int> d[maxn], det, ver, G[maxn];void add(int x, int st, int now) {if(st == d[x].size()) return sum[now] += mu[now], void();return add(x, st + 1, now), add(x, st + 1, now * d[x][st]);
}
void del(int x, int st, int now) {if(st == d[x].size()) return sum[now] = 0, void();return del(x, st + 1, now), del(x, st + 1, now * d[x][st]);
}
int qry(int x, int st, int now) {if(st == d[x].size()) return sum[now];return qry(x, st + 1, now) + qry(x, st + 1, now * d[x][st]);
}
void solve(int l, int r, std::vector<int> v) {if(l == r) {for(auto& x : v)G[l].pb(x);return ;}int mid = (l + r) >> 1;for(int i = l;i <= mid;++ i)add(det[i], 0, 1);std::vector<int> lqry, rqry;for(auto& x : v) {if(qry(x, 0, 1)) lqry.pb(x);else rqry.pb(x);}for(int i = l;i <= mid;++ i)del(det[i], 0, 1);return solve(l, mid, lqry), solve(mid + 1, r, rqry);
}int main() {scanf("%d %d", &n, &k); init(N);for(int i = 1;i <= n;++ i) {scanf("%d", &a[i]); int x = a[i];for(int j = 1;j <= cnt;++ j) {if(prime[j] * prime[j] > x) break ;if(x % prime[j]) continue ;while(x % prime[j] == 0) x /= prime[j];d[i].pb(prime[j]);}if(x > 1) d[i].pb(x);if(!qry(i, 0, 1)) add(i, 0, 1), det.pb(i);else ver.pb(i);}for(auto& x : det)del(x, 0, 1);int m = det.size() - 1; if(m + 1 >= k) {int t = 0;for(auto& x : det) {printf("%d ", x);++ t; if(t >= k) break ;}return 0;}solve(0, m, ver); std::iota(ord, ord + m, 0);std::sort(ord, ord + m, [&](const int& lhs, const int& rhs) {return G[lhs].size() > G[rhs].size();});int t = 0;for(int i = 0;i <= m;++ i) {t += G[ord[i]].size() + 1;if(t >= k) {std::vector<int> opt;for(int j = 0;j <= i;++ j)opt.pb(det[ord[j]]), opt.pb(G[ord[j]].back()), G[ord[j]].pop_back();for(int j = 0;j <= i;++ j)while(opt.size() < k&&!G[ord[j]].empty())opt.pb(G[ord[j]].back()), G[ord[j]].pop_back();for(auto& x : opt)printf("%d ", x);puts(""); return 0;}}return 0;
}
