解説
この問題は、 O(NlogNQ) の計算量で解くことができます。
TLE 解 O(NQlogN)
まずは、ほぼ愚直にソートしてみます。
当然これだと TLE するため、高速化を考える必要があります。
高速化
まず、 A を j=1,2,…,Q について AimodBj でソートするのは、 A を [AimodBQ,AimodBQ−1,…,AimodB1] の辞書順でソートするのと同値になります。
辞書順の比較では、どこかで違う値が出てくればそこでやめても構いません。
そのため、辞書順の比較にすると高速化になります。
この比較の最悪ケースは、ずっと同じ値が続く場合です。
そのような場合について、対策を考えてみます。
- Ai1 と Ai2 を B の最小公倍数で割ったあまりが等しい場合
- あまりが同じ値の個数を数えておいて、 unique すれば後で復元できる
- Bj がすべて等しい場合
- B を後ろから unique しても答えは変わらない
- Bj が Bj+1 の倍数である場合
- 最大で log2109≈30 程度しか続かないので無視できる
- Bj が Ai より大きい場合
このように考えると、 Bj が Ai より大きい場合だけが問題であることがわかります。
平方分割
B を昇順にソートしたものを B′ とします。
前処理として、 k=1,2,…,⌊Q⌋ に対して、 Ck を、 B から BkQ′ より大きい要素を取り除いたものとします。これには O(QQ) かかります。
このようにして、ソートするときに B の代わりに二分探索で最適に選んだ Ck を使うと、同じあまりは最大で Q 個しか存在しえないため、 O(NlogNQ) でソートできます。