冒个泡(?
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 second
using 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;
}