No.752 mod数列 - D言語で競プロ

No.752 mod数列 - yukicoder

問題

数列
$a_i = P \% i (i = 1, 2, 3, \dots)$
が与えられる。

$Q$ 個のクエリ $(L_j, R_j)$ に対して
$\sum_{i = L_j}^{R_j} a_i$ を求めよ。

制約

$1 \leq P \leq 10^9$
$1 \leq Q \leq 10^5$
$1 \leq L_j \leq R_j \leq 10^9$

解法

まずおなじみの累積和テクニックの考え方から

$\sum_{i = L_j}^{R_j} a_i = \sum_{i = 1}^{R_j} a_i - \sum_{i=1}^{L_j - 1} a_i$

が成り立つので、任意の $R$ に対して

$\sum_{i = 1}^{R} a_i$

を求めるにはどうすればよいか？を考えることにします。

ここで $R \leq 10^5$ 程度までであれば単純に累積和でやればいいんですが、今回は $R \leq 10^9$ ですので一筋縄ではいかなさそうです。まずいきなり和を考えるのではなくて、数列 $a_i$ がどのようになっているかを考えてみることにします。自明ではあるが重要なこととして、 $i > P \Rightarrow a_i = P$ となっていることが分かります。よって $i \leq P$ だけで考えてみることにします。

こういうのは小さな具体例から考えてみるとよいので、 $P = 24$ として $a_i$ がどのようになるかを見てみます。

i	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24
$a_i$	0	0	0	0	4	0	3	0	6	4	2	0	11	10	9	8	7	6	5	4	3	2	1	0

すると一つ分かりやすい法則が見えます。 $i = 13, 14, 15, \dots$ となるにしたがって $a_i$ は一つずつ減っていくことが分かります。このことを式で表すと $P > i > P / 2 \Rightarrow a_i = P - i$ となるということが分かります。さらに $i = 9, 10, 11$ にも着目するとここでも規則性が見えて、 $a_i$ が2ずつ減っていくことが見て取れます。これも式で表すと $P/2 > i > P / 3 \Rightarrow a_i = P - 2i$ となることが分かります。

ここまで分かると一般化することが出来て、最初の自明な事実 $i > P \Rightarrow a_i = P$ も合わせると、

任意の $k = 0, 1, 2, \dots$ に対して $P / k > i > P / (k + 1) \Rightarrow a_i = P - ki$

と表せることが分かります。ここで $k = 0$ のとき $P / 0 = \infty$ と考えることにするとつじつまが合います。

そしてこれが分かると、 $k$ を固定したときの区間 $(P/(k+1), P/K)$ に含まれる $i$ に関する $a_i$ の総和というのは簡単に分かります。 $P$ は単に区間の長さ倍すればよく $ki$ の部分はおなじみの $\sum_{i = 1}^{N} i = N(N-1)/2$ という公式を使えばよいからです。

さて、この事実が分かると何がよいのでしょうか？
任意の $k = 0, 1, 2, \dots$ に対して $P / k > i > P / (k + 1) \Rightarrow a_i = P - ki$ で、この区間に対して $a_i$ の和は $O(1)$ で求められます。なので $k = 0, 1, 2, \dots, P$ と回せばいいわけですが、 $P \leq 10^9$ までなのでこれでは計算量の削減になっていません。
しかし、 $k = 1, 2, \dots, 9999$ までやるとしてみましょう。すると $i > P / 10^4$ の部分に対してはこれで求められて、残りの $i \leq P / 10^4$ の部分は累積和で求めてやることにすると計算量が良い感じに収まることが分かります。
後は和の上限が指定した $R$ を超えないように適宜区切ったりなんやかんやする必要がありますが、大筋のアイデアはこんな感じで計算量は今回は適当に $10^4$ とかにしましたが一般には $\sqrt{P}$ くらいにするのがいいので $O(Q + \sqrt{P})$ に出来ます。

感想

計算量にルートが出てくる問題ってあまり無い気がして面白かったので久々に書きました。