読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

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