Educational Codeforces #18: E. Colored Balls
http://codeforces.com/contest/792/problem/E
解法
a[0] を d 分割するとき、\(\lfloor(a_0/d)\rfloor\)と\(\lceil(a_0/d)\rceil\) を作ることになる。したがって、最終的な集合の最小値は \(\lfloor(a_0/d)\rfloor -1, \lfloor(a_0/d)\rfloor \) 以外にはならない。最小値を決め打ちすればよい。
以下、補足。
補足
\( \lfloor n/1\rfloor, \lfloor n/2\rfloor, \lfloor n/3\rfloor, \ldots, \lfloor n/n\rfloor \) が取りうる値の種類数は \(O(\sqrt{n})\) である。
\( \lfloor n/i \rfloor = v \) を満たすような $i$ の範囲は $\lfloor n/(v+1)\rfloor\lt i \le
\lfloor n/v\rfloor$ である。
O(√n) 個で表せることだけ分かっても不十分で、各値を取る区間も求める必要があることが多い。
おまけ
以上の性質を使うと、たとえば以下の関数を高速に計算できる。
\[ \sum_{i=1}^{n} \left\lfloor \frac{n}{i} \right\rfloor i \]
// オーバーフローするので注意 long long sum(long long n) { long long ret = 0; for (long long i = 1; i * i <= n; i++) { long long l = n / (i + 1); long long r = n / i; ret += i * (r * (r + 1) / 2 - l * (l + 1) / 2); if (i <= l) { ret += n / i * i; } } return ret; }
変な関数を持ってきたわけではなくて、普通に出てくる式である。
\[ \sum_{i=1}^{n} \left\lfloor \frac{n}{i} \right\rfloor i = \sum_{i=1}^{n} \sum_{d \mid i} d \]