解説

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

TLE 解 $O(NQ \log N)$

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

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

高速化

まず、 $A$ を $j = 1, 2, \ldots, Q$ について $A_i \bmod B_j$ でソートするのは、 $A$ を $[A_i \bmod B_Q, A_i \bmod B_{Q - 1}, \ldots, A_i \bmod B_1]$ の辞書順でソートするのと同値になります。

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

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

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

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

平方分割

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

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

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