ABC466 F - Many Mod Calculation

考え方

$1$ 以上 $X$ 以下の全ての数に対して処理を行ったときに、どういう値が何個あるのか持てばよい。
もちろん、愚直にやっては $O(X)$ 個の情報をもつことになって、計算量もメモリも足らない。

そこで、特殊な圧縮をしてデータを持つことにする。
つまり、「$0$ 以上 $k$ 未満の値が $1$ つずつある」みたいな形で持つ。
すると、このカタマリを A[i] で割った余りも、類似の形式複数個で表現できる。
具体的には、「$0$ 以上 $k$ 未満の値が $l$ 個ずつある」データを $a$ で割る場合は、以下。

• 「$0$ 以上 $a$ 未満の値が $\lfloor k/a \rfloor \times l$ 個ずつある」
• 「$0$ 以上 $k \bmod a$ 未満の値が $l$ 個ずつある」

あとはこれを、同じ範囲のものは可能な限りデータをまとめていく工夫をすればよい。
範囲が A[i] を超えるものの抽出は、priority_queue などを用いればよい。

与えられる問題は $0$ 以上ではなく $1$ 以上であるため、そこだけ困ったように見える。
が、「$0$ 以上 $1$ 未満の値が $-1$ 個ずつある」を入れておくことで解消できる。
しかも、これが番兵として機能してくれるため、コード的にも都合がいい。

計算量の見積もりは非常に難しいが、中途半端な長さのデータは最大でも $O(N)$ 個しか出てこない。
また、$1$ つのデータの幅は、剰余を $1$ 回とられるたびに半分未満になる。
これらのことから、全体で $O(N \log N \log X)$ であるため、間に合う。

入力例1での動作

$1$ つめのテストケースのみ。
入力を受け取る。

n: 3
x: 7
a: {5, 2, 3}

最初は、$1$ 以上 $7$ 以下が $1$ 個ずつある状態を、次の $2$ つの区間で表す。

[0,8): 1個
[0,1): -1個

まず $5$ で余りを取る。
$[0,8)$ は、$0$ から $4$ が $1$ 周分と、$0$ から $2$ がもう $1$ 周分現れる。

[0,8): 1個
  -> [0,5): 1個
  -> [0,3): 1個

$[0,1)$ はそのままなので、この時点の状態は次のようになる。

[0,5): 1個
[0,3): 1個
[0,1): -1個

次に $2$ で余りを取る。
$[0,5)$ からは $[0,2)$ が $2$ 個と $[0,1)$ が $1$ 個できる。
$[0,3)$ からは $[0,2)$ が $1$ 個と $[0,1)$ が $1$ 個できる。

既にあった $[0,1)$ の $-1$ 個も合わせると、同じ区間をまとめた状態は次のようになる。

[0,2): 3個
[0,1): 1個

最後に $3$ で余りを取る。
どちらの区間も上限が $3$ 以下なので、状態は変化しない。

[0,2): 3個
[0,1): 1個

どの区間にも $0$ が $1$ つずつ含まれる。
したがって、最終的に $0$ となる数の個数は $3+1=4$ であり、答えは $4$ となる。

注意点

$X$ や $A_i$ は、int 型からはみ出る。
long long 型を用いること。

別解

特になし。