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/1\rfloor, \lfloor n/2\rfloor, \lfloor n/3\rfloor, \ldots, \lfloor n/\sqrt{n} \rfloor $ は $\sqrt{n}$ 個しかないのだから$ \sqrt{n} $ 種類以下である。 $ \lfloor n/(\sqrt{n}+1)\rfloor, \lfloor n/(\sqrt{n}+2)\rfloor, \ldots, \lfloor n/n \rfloor $ はどれも $\sqrt{n}$ 以下の数なので $ \sqrt{n} $ 種類以下である。したがって全体で高々 $ 2\sqrt{n} $ 種類である。

$ \lfloor n/i \rfloor = v $ を満たすような $i$ の範囲は $\lfloor n/(v+1)\rfloor\lt i \le
\lfloor n/v\rfloor$ である。

$ \lfloor n/i \rfloor = v $を満たすとき、$ v \le n/i \lt v+1 $ である。このことから容易に分かる。

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 \]