\(1\) 以上 \(2M\) 以下の整数で良い集合を構築する際、\(M\) 個の各奇数 \(n=1,\ 3,\ \dots,\ 2M-1\) に対し、 \(2^kn\) からは高々 \(1\) つしか選べません。

このため、要素数が \(M\) であるような良い集合を選ぶことは \(k_1,\ k_3,\ \dots,\ k_{2M-1}\) を以下の条件を満たすように選ぶことと同じです。

• $2^{k_n}n \in S$
• $n\neq m$ のとき $2^{k_n}n$ は $2^{k_m}m$ の倍数ではない

さらに \(2\) 番目の条件は \(n\) が \(m\) の倍数でない場合は必ず満たされることを考えると、「\(n\) が \(m\ (n\neq m)\) の倍数ならば \(k_n< k_m\)」と言い換えられます。

このような \(k_n\) を選ぶのは典型的な問題で \(n=1,\ 3,\ \dots,\ 2M-1\) の順に \(k_n\) ができるだけ大きくなるように決めると各 \(k_n\) の上界 \(R_n\) が得られます。同様に、 \(n=2M-1,\ 2M-3,\ \dots,\ 1\) の順に \(k_n\) をできるだけ小さくするように決めると各 \(k_n\) の下界 \(L_n\) が得られます。

さて、各 \(n=1,\ 3,\ \dots,\ 2M-1\) について、 \(k_n=K\) とできるような \(K\) の条件を考えると、 \(L_n\le K \le R_n\) かつ \(2^Kn \in S\) のときはよい集合が必ず構築できます。これは \((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})\) とすれば条件を満たすからです。

よって \(L_n\ R_n\) が求まれば条件判定が可能で、これを求めるのは \(O(N+M\log M)\) や \(O(N+M\log \log M)\)などでできます。