Gold Experience
Contest: Codeforces Global Round 3
Difficulty rating: 3300
Tags: constructive algorithms, graphs, math, number theory, probabilities

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 format:
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 format:
Print exactly $$$k$$$ distinct integers — the indices of the vertices in the chosen set in any order.

Constraints:
Time limit: 2.0 s
Memory limit: 1024.0 MB

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.

Example input:
6 3
6 15 10 8 14 12

Example output:
1 3 6

Example input:
8 4
11 15 10 6 21 15 10 6

Example output:
1 2 3 4

Editorial:
Firstly, let's discuss how to find the answer in $$$O(N^2)$$$ time. Let's assume $$$k$$$ is even. Pick any set on $$$k$$$ vertices. If it is a clique, just print it as an answer, if it is not, there must be two vertices in this set that don't share an edge. Just remove these two vertices and replace them with 2 arbitrary ones from the rest of the vertices. We can notice that if we remove $$$\frac{k}{2}$$$ such pairs, then removed vertices will form a set where all vertices are not fair.
If $$$k$$$ is odd, then the above algorithm has a problem, because we remove two vertices in one step. To fix it, we can find a triplet of vertices $$$a$$$, $$$b$$$, $$$c$$$ such that there is no edge between $$$a$$$ and $$$b$$$, and there is no edge between $$$b$$$, and $$$c$$$. Now, with this triplet we can get the set with odd size. If there are no such triplet, then, our graph has quite simple structure which we can handle separately.
Now to the $$$O(N \cdot Log \cdot 2^8)$$$ solution.
1. Assume we have a set of integers $$$a_1, a_2, \ldots, a_n$$$ and an integer $$$x$$$. We want to find, for how many $$$a_i$$$ have $$$gcd(a_i, x) \neq 1$$$. This can be done using inclusion-exclusion principle. Let $$$p_1, p_2, \ldots, p_k$$$ be distinct prime divisors of $$$x$$$. At first, we want to count how many $$$a_i$$$ is divisible by $$$p_1, p_2, \ldots, p_k$$$, but than $$$a_i$$$'s divisible by both $$$p_1, p_2$$$ are counted twice, so we subtract count of $$$a_i$$$ that is divisible by $$$p_1 \cdot p_2$$$ and so on. We can maintain set $$$a_1, a_2, \ldots, a_n$$$ and answer queries dynamically in $$$O(2^{NumberOfPrimeDivisors})$$$ time. This is the only place where we use the graph structure defined by the edge between two vertices $$$i$$$ and $$$j$$$ exists if only if $$$gcd(a_i, a_j) \neq 1$$$.
2. Like in $$$O(N^2)$$$ solution, let's find a triplet of vertices $$$a$$$, $$$b$$$, $$$c$$$ such that there is no edge between $$$a$$$ and $$$b$$$, and there is no edge between $$$b$$$ and $$$c$$$. Let's remove this triplet from the graph.
3. Let $$$b$$$ be the number of vertices that are connected to all other $$$n - 3$$$ vertices. If $$$b \geq k$$$ we can print any $$$k$$$ of them as a clique. Otherwise, let's remove all of these $$$b$$$ vertices. We can notice that remaining vertices plus removed triplet form an antifair set. Let's estimate size of this set: $$$S = (n - 3) - b + 3 = n - b$$$. Recall that $$$b \le k$$$ and $$$2 \cdot k \leq n$$$, so we have $$$S = n - b \geq k$$$. So, now we get an antifair set of size equal to $$$k$$$ or greater than $$$k$$$. Let's show that we always can construct an antifair set with size strictly equal to $$$k$$$.
4. In the previous paragraph we have estimated the maximum size of an antifair set on vertices $$$1, 2, \ldots, n - 3$$$. Let $$$f(R)$$$ be the maximum size of an antifair set on vertices with indices: $$$1, 2, \ldots, R$$$. Let's find with binary search lowest integer $$$c$$$ such that $$$f(c - 1) + 3 < k$$$ and $$$f(c) + 3 \geq k$$$. Let's look at the vertex $$$c$$$. The size of the maximal antifair set without it is $$$f(c - 1)$$$. The size of the maximal antifair set with it is $$$f(c)$$$. So among vertices $$$1, 2, \ldots, c - 1$$$ there are exactly $$$f(c) - f(c - 1) - 1$$$ of them connected with all vertices from $$$1$$$ to $$$c - 1$$$ and not connected with the vertex $$$c$$$. It is easy to see, that we can delete any $$$f(c) - f(c - 1) - 2$$$ of them or less and the remaining set of vertices will still be antifair. With this observation we can achieve either set of size $$$k$$$ or set of size $$$k + 1$$$. In the first case, we just find the answer. In the second case, remember, that we have reserved triplet and can delete one of it's vertex to make the total size $$$k$$$.