Educational Codeforces Round 5 E. Sum of Remainders
毎回 Educational の E 問題ぐらいになるとパッと解けない。
問題文
問題概要
整数 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 ...