AOJ 0270 Modular Query モジュロ・クエリ

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0270

カードが6, 7, 11, 13, 14, 15, 16, 19で，q=5のクエリに答えたいとする。

5で割った余りが最大になり得るのは，5*1のlower_boundの1つ前，5*2のlower_boundの1つ前，……，なので，ソートしておいて二分探索する方法，set.lower_boundを使う方法，累積和的な方法などで調べられる (下の図の例のように「5*1のlower_boundの1つ前」の要素が無い場合もあるので注意する)。

f:id:kujira16:20150823132241p:plain

この方法を使ったときの1クエリあたりの計算量を考えると，二分探索的な方法ではO(log N)の探索をceil(N/q)回，累積和的な方法ではO(1)の探索をceil(N/q)回行うことになる。クエリは10⁵個まで与えられるので，これでは間に合わないような気がしてしまうが，ここで「同じ数を 2 回以上質問することはありません」という条件が活用できないか考えてみよう．

ceil(N/q)はqが小さいほど大きくなるので，最悪ケースとしてクエリqが1〜Qの整数それぞれ1つずつだった場合を考える。探索に二分探索的な方法を使ったとして，計算量は以下のようになる。

${\displaystyle \sum_{q=1}^Q \frac{N}{q} \log N=N\log N \sum_{q=1}^Q \frac{1}{q} }$