Consider an undirected graph $G$ with $n$ vertices. There is a value $a_i$ in each vertex.
Two vertices $i$ and $j$ are connected with an edge if and only if $gcd(a_i, a_j) > 1$, where $gcd(x, y)$ denotes the greatest common divisor (GCD) of integers $x$ and $y$.
Consider a set of vertices. Let’s call a vertex in this set fair if it is connected with an edge with all other vertices in this set.
You need to find a set of $k$ vertices (where $k$ is a given integer, $2 \cdot k \le n$) where all vertices are fair or all vertices are not fair. One can show that such a set always exists.
Input
The first line contains integers $n$ and $k$ ($6 \leq 2 \cdot k \leq n \leq 10^5$) — the number of vertices and parameter $k$.
The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($2 \le a_i \le 10^7$) — the values in the vertices.
Output
Print exactly $k$ distinct integers — the indices of the vertices in the chosen set in any order.
Examples
input
6 3 6 15 10 8 14 12
output
2 4 5
input
8 4 11 15 10 6 21 15 10 6
output
5 7 1 2
input
10 5 3003 17017 3230 49742 546 41990 17765 570 21945 36465
output
1 2 4 5 6
Note
In the first test case, set $\{2, 4, 5\}$ is an example of set where no vertices are fair. The vertex $2$ does not share an edge with vertex $4$ since $gcd(15, 8) = 1$. The vertex $4$ does not share an edge with vertex $2$. The vertex $5$ does not share an edge with vertex $2$.
In the second test case, set $\{8, 5, 6, 4\}$ is an example of a set where all vertices are fair.
Solution:
#include <bits/stdc++.h>
using namespace std;
string to_string(string s) {
return '"' + s + '"';
}
string to_string(const char* s) {
return to_string((string) s);
}
string to_string(bool b) {
return (b ? "true" : "false");
}
template <typename A, typename B>
string to_string(pair<A, B> p) {
return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A>
string to_string(A v) {
bool first = true;
string res = "{";
for (const auto &x : v) {
if (!first) {
res += ", ";
}
first = false;
res += to_string(x);
}
res += "}";
return res;
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
cerr << " " << to_string(H);
debug_out(T...);
}
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif
vector<int> least = {0, 1};
vector<int> primes;
int precalculated = 1;
void RunLinearSieve(int n) {
n = max(n, 1);
least.assign(n + 1, 0);
primes.clear();
for (int i = 2; i <= n; i++) {
if (least[i] == 0) {
least[i] = i;
primes.push_back(i);
}
for (int x : primes) {
if (x > least[i] || i * x > n) {
break;
}
least[i * x] = x;
}
}
precalculated = n;
}
const int N = 100010;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
int mx = *max_element(a.begin(), a.end());
RunLinearSieve(mx);
vector<int> pid(mx + 1, -1);
int pcnt = 0;
vector<vector<int>> z(n);
for (int i = 0; i < n; i++) {
int x = a[i];
int y = 1;
int last = -1;
while (x > 1) {
if (least[x] != last) {
y *= least[x];
if (pid[least[x]] == -1) {
pid[least[x]] = pcnt++;
}
z[i].push_back(pid[least[x]]);
last = least[x];
}
x /= least[x];
}
a[i] = y;
}
debug(a);
vector<vector<int>> ids(pcnt);
for (int i = 0; i < n; i++) {
for (int j : z[i]) {
ids[j].push_back(i);
}
}
vector<bitset<N>> bitsets;
vector<int> bitset_id(pcnt, -1);
for (int i = 0; i < pcnt; i++) {
if ((int) ids[i].size() >= n / 239) {
bitset_id[i] = (int) bitsets.size();
bitsets.emplace_back();
for (int j : ids[i]) {
bitsets.back()[j] = 1;
}
}
}
bitset<N> alive;
for (int i = 0; i < n; i++) {
alive[i] = 1;
}
vector<char> visited_value(mx + 1, 0);
vector<vector<int>> comps;
vector<int> alone;
for (int st = 0; st < n; st++) {
if (alive[st] == 0) {
continue;
}
vector<int> que(1, st);
alive[st] = 0;
for (int b = 0; b < (int) que.size(); b++) {
int i = que[b];
if (visited_value[a[i]]) {
continue;
}
visited_value[a[i]] = 1;
bitset<N> go = alive;
for (int j : z[i]) {
if (bitset_id[j] == -1) {
for (int u : ids[j]) {
go[u] = 0;
}
} else {
go ^= (go & bitsets[bitset_id[j]]);
}
}
for (int u = go._Find_first(); u < n; u = go._Find_next(u)) {
que.push_back(u);
alive[u] = 0;
}
}
debug(que);
if (que.size() == 1) {
alone.push_back(que[0]);
} else {
comps.push_back(que);
}
}
vector<int> ret;
if ((int) alone.size() + (int) comps.size() >= k) {
for (auto& c : comps) {
alone.push_back(c[0]);
}
alone.resize(k);
ret = alone;
} else {
vector<int> order(comps.size());
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(), [&](int i, int j) {
return comps[i].size() > comps[j].size();
});
int take = 0;
int sum = 0;
while (sum < k - 1) {
sum += (int) comps[order[take]].size();
take++;
}
if (sum == k - 1) {
comps[order[0]].pop_back();
}
for (int i : order) {
for (int u : comps[i]) {
ret.push_back(u);
}
}
}
for (int i = 0; i < k; i++) {
if (i > 0) {
cout << " ";
}
cout << ret[i] + 1;
}
cout << '\n';
return 0;
}
