Educational Codeforces Round 5 E. Sum of Remainders

毎回 Educational の E 問題ぐらいになるとパッと解けない。

問題文

codeforces.com

問題概要

整数 n, m が与えられるので、n mod 1 + n mod 2 + ... + n mod m を求めよ。

解法

$n \bmod i = n - \lfloor n/i \rfloor i$ なので、求める値は

$$ nm - \left( \left\lfloor \frac{n}{1} \right\rfloor \cdot 1 + \left\lfloor \frac{n}{2} \right\rfloor \cdot 2 + \left\lfloor \frac{n}{3} \right\rfloor \cdot 3 + \cdots + \left\lfloor \frac{n}{m} \right\rfloor \cdot m \right)$$

になる。 $\lfloor n/i \rfloor$ の取りうる値は $O(\sqrt{n})$ 通りしかないので、 $\lfloor n/i \rfloor$ が等しい区間をまとめて計算すると速い。

なぜ floor(n/i) の取りうる値が O(√n) 通りになるのか

$$ \underbrace{ \left\lfloor \frac{n}{1} \right\rfloor,\, \left\lfloor \frac{n}{2} \right\rfloor,\, \ldots,\, \left\lfloor \frac{n}{\sqrt{n}} \right\rfloor}_{O(\sqrt{n})},\, \underbrace{ \left\lfloor \frac{n}{\sqrt{n}+1} \right\rfloor,\, \ldots,\, \left\lfloor \frac{n}{n - 1} \right\rfloor,\, \left\lfloor \frac{n}{n} \right\rfloor}_{O(\sqrt{n})} $$

前半は $\sqrt{n}$ 項しかないのだから $O(\sqrt{n})$ 通りしかなく、後半も $1$ から $\sqrt{n}$ の値しか取り得ないので $O(\sqrt{n})$ 通りしかない。

実装

同じ値を取る区間は、 i が小さいときは愚直に、iが大きいときは二分探索で求めた。 Editorial を見るともっと頭のいい求め方が書いてある。

mod の取り忘れに注意。

Educational Codeforces Round 5 E. Sum of Remainder ...

floor(n/i) の取りうる値を調べてみたら最大でも600万通り程度だったのでこの方針で攻めた。 重要な性質っぽいので抑えておきたい。