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}

最初に、[0,8) を $1$ 個、[0,1) を $-1$ 個入れる。
これにより、整数 $1$ 以上 $7$ 以下が $1$ 個ずつある状態を表す。

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

a[0]=5 で余りを取る。

[0,8) は、[0,5) が $1$ 個と、端数の [0,3) が $1$ 個に分かれる。
[0,1) は上限が $5$ 以下なので変化しない。

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

a[1]=2 で余りを取る。

[0,5) は、[0,2) が $2$ 個と、端数の [0,1) が $1$ 個に分かれる。
[0,3) は、[0,2) が $1$ 個と、端数の [0,1) が $1$ 個に分かれる。

同じ区間をまとめると、次のようになる。

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

a[2]=3 で余りを取る。
すべての区間の上限が $3$ 以下なので、状態は変化しない。

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

すべての区間には 0 が $1$ 個ずつ含まれる。
よって、区間の個数の合計が答えになる。

result: 3+1
      = 4

注意点

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

別解

特になし。