解説

この問題は、 O(NlogNQ)O(N \log N \sqrt{Q}) の計算量で解くことができます。

TLE 解 O(NQlogN)O(NQ \log N)

まずは、ほぼ愚直にソートしてみます。

当然これだと TLE するため、高速化を考える必要があります。

高速化

まず、 AAj=1,2,,Qj = 1, 2, \ldots, Q について AimodBjA_i \bmod B_j でソートするのは、 AA[AimodBQ,AimodBQ1,,AimodB1][A_i \bmod B_Q, A_i \bmod B_{Q - 1}, \ldots, A_i \bmod B_1] の辞書順でソートするのと同値になります。

辞書順の比較では、どこかで違う値が出てくればそこでやめても構いません。 そのため、辞書順の比較にすると高速化になります。

この比較の最悪ケースは、ずっと同じ値が続く場合です。 そのような場合について、対策を考えてみます。

  • Ai1A_{i1}Ai2A_{i2}BB の最小公倍数で割ったあまりが等しい場合
    • あまりが同じ値の個数を数えておいて、 unique すれば後で復元できる
  • BjB_j がすべて等しい場合
    • BB を後ろから unique しても答えは変わらない
  • BjB_jBj+1B_{j + 1} の倍数である場合
    • 最大で log210930\log_2 10^9 \approx 30 程度しか続かないので無視できる
  • BjB_jAiA_i より大きい場合
    • 困った…

このように考えると、 BjB_jAiA_i より大きい場合だけが問題であることがわかります。

平方分割

BB を昇順にソートしたものを BB' とします。

前処理として、 k=1,2,,Qk = 1, 2, \ldots, \lfloor\sqrt{Q}\rfloor に対して、 CkC_k を、 BB から BkQB'_{k\sqrt{Q}} より大きい要素を取り除いたものとします。これには O(QQ)O(Q \sqrt Q) かかります。

このようにして、ソートするときに BB の代わりに二分探索で最適に選んだ CkC_k を使うと、同じあまりは最大で Q\sqrt{Q} 個しか存在しえないため、 O(NlogNQ)O(N \log N \sqrt Q) でソートできます。