\(d = 1, 2, \dots 30\) に対して、以下を満たす正整数の組 \(1\leq i < j \leq N\) が求まれば良いです。

• \(A_{i} + A_{j}\) が \(2^{d}\) で割り切れる

これは \(A_{i}\) を \(2^{d}\) で割った余りが昇順ソートされた列があれば、ラングレス圧縮と尺取り法を用いて \(O(N)\) で求めることができます。

c++ 実装例 174 ms

この実装の計算量はソートする部分がボトルネックとなり、\(O(N\log(N)\log(\max(A)))\) です。

このソートする部分はラディックスソートを \(2\) 進法でやっている途中と変わらないため、ソート部分は 1 step ごとに \(O(N)\) に改善できるので、計算量は \(O(N\log(\max(A)))\) に改善できます。

c++ 実装例 103 ms