CodeForces Round #382 (Div. 1): B. Taxes

http://codeforces.com/contest/736/problem/B

問題概要

$n$円の収入に対して、$n$未満の最大の約数だけ税金がかかる。後の説明のために税金額を$f(n)$と書くことにする。

Mr. Funt は税金の額をごまかすために、$n$をいくつかの整数$n_1,n_2,\ldots,n_k$に分割する($k=1$も許される)。ただし$n_i \ge 2$ でなければならない。このときの税金は$\sum_i f(n_i)$となる。

税金の最小値は何になるだろうか。

  • $2 \le n \le 2\cdot 10^9$

解法

以下の事実に気付くことができれば解くことができる。

ゴールドバッハの予想に関しては、Wikipedia によれば 2012 年現在、4×1018 までの偶数で成り立つことが確認されているそうだ。

以上の事実を用いれば次のように解くことができる。

(1) n が素数のときは 1
(2) n が4以上の偶数のときは 2
(3) n-2 が素数のときは 2
(4) それ以外は 3

(1),(2)は前述したとおりである。(3)のときが2になるのも確かにそうである。

(4) のケースは n-3 が偶数になることを利用すると、ゴールドバッハの予想より n=3+p+q という分解が存在することが分かる。 また、奇素数2つの和が偶数になることから、2は達成できないこともわかる。つまり3が最小である。

多少知識ゲー感はあるかな。「素数 和」で調べれば出てくる話ではある。