When constructing a good set with integers between \(1\) and \(2M\), for each of the \(M\) odd numbers \(n=1,\ 3,\ \dots,\ 2M-1\), we can choose at most one from the numbers \(2^kn\).

Thus, choosing a good set with \(M\) elements is equivalent to choose \(k_1,\ k_3,\ \dots,\ k_{2M-1}\) for each \(n=1,\ 3,\ \dots,\ 2M-1\) so that the following conditions are satisfied.

• $2^{k_n}n \in S$.
• $2^{k_n}n$ is not a multiple of $2^{k_m}m$, if $n\neq m$.

Moreover, considering that the second condition is always satisfied if \(n\) is not a multiple of \(m\), it is equivalent to “\(k_n< k_m\) if \(n\) is a multiple of \(m\) \((n\neq m)\).”

Choosing such \(k_n\)’s is a typical problem: we get the upper limit \(R_n\) for each \(k_n\) by choosing as large \(k_n\) as possible in the order \(n=1,\ 3,\ \dots,\ 2M-1\), and the lower limit \(L_n\) for each \(k_n\) by choosing as small \(k_n\) as possible in the order \(n=2M-1,\ 2M-3,\ \dots,\ 1\).

Now, for each \(n=1,\ 3,\ \dots,\ 2M-1\), when can we have \(k_n=K\)? It turns out to be always possible when \(L_n\le K \le R_n\) and \(2^Kn \in S\), because \((k_1,\ k_3,\ \dots,\ k_{n-2},\ k_n,\ k_{n+2},\ \dots,\ k_{2M-3},\ k_{2M-1})=(R_1,\ R_3,\ \dots,\ R_{n-2},\ K,\ L_{n+2},\ \dots,\ L_{2M-3},\ L_{2M-1})\) is a feasible option.

Therefore, the problem is solved by finding \(L_n\) and \(R_n\), which can be done in \(O(N+M\log M)\) or \(O(N+M\log \log M)\) time.