Xmas Contest 2019 E: Sum of f(n) 解説

https://atcoder.jp/contests/xmascon19/tasks/xmascon19_e

問題概要

 n の素因数の個数 (重複込み) を  f(n) とする. N が与えられるので  \sum_{n=1}^N f(n) を求めよ.

解法 1 (?)

答えを手元で全部計算して,適当な間隔で区切って埋め込みます.狭い区間については区間篩のアルゴリズム f を効率的に計算できる (素数  p で篩うときに  p で割り切れる回数だけ  1 を足す) ので,これで正解することができます.

終わる確信があったら,手元で D 問題と一緒に計算するとよいと思います! D 問題より桁数が多かったり時間制限が短かったりでちょっとだけ大変かもしれません.

解法 2

素数  p の影響が何回足されるかを考えると,各  p について, N 以下の  p の倍数の個数, p^2 の倍数の個数, p^3 の倍数の個数,……を足していけば答えになります. p^2 以降の倍数が現れるのは  p \le \sqrt{N} なもののみなので,それらについてはひとつずつ処理できます.これで,あとは  \sum_{p:素数} \lfloor\frac{N}{p}\rfloor を求めればよくなりました.

 \lfloor\frac{N}{p}\rfloor の値は  2 \sqrt{N} 通りくらいしかないので,同じ値になる部分をまとめて計算したいです. \lfloor\frac{N}{p}\rfloor = k \iff \lfloor\frac{N}{k+1}\rfloor \lt p \le \lfloor\frac{N}{k}\rfloor なので,「 \lfloor\frac{N}{k}\rfloor 以下の素数の個数」という形のものが数えられれば, \sum_p \lfloor\frac{N}{p}\rfloor = \sum_k (\pi(\lfloor\frac{N}{k}\rfloor) - \pi(\lfloor\frac{N}{k+1}\rfloor)) k と計算できます ( \pi(n) n 以下の素数の個数).

これは,賢い DP をするとできます.素数を小さい順に  p_1, p_2, \ldots とします. g(i, n) を, n 以下の正の整数であって  p_1, \ldots, p_i のいずれでも割り切れないものの個数とおきます. g(i, n) = g(i - 1, n) - g(i - 1, \lfloor\frac{n}{p_i}\rfloor) という漸化式が成り立ちます. \pi(n) = g(\pi(\sqrt{n}), n) - 1 なので, \pi(\lfloor\frac{N}{k}\rfloor) の形のものを計算するのに必要な  g(i, n) はやはり  n = \lfloor\frac{N}{k}\rfloor の形をしています.

このままだとまだ遅いので高速化します. g(i - 1, n) から  g(i, n) への変化に注目すると, n \lt p_i では変わらず, p_i \le n \lt p_i^2 では  1 減るだけになっています.ということをふまえて  g'(i, n) = g(i, n) + \min\{i, \pi(n)\} とおき直すと, n \lt p_i^2 では  g'(i, n) = g'(i - 1, n) n \ge p_i^2 では  g'(i, n) = g'(i - 1, n) - g'(i - 1, \lfloor\frac{n}{p_i}\rfloor) + i となります.これで DP 配列を使い回して  n \ge p_i^2 の部分のみ更新すればよいことになります.なお, g'(i, n) n 以下の正の整数に対して Eratosthenes の篩で  p_1, \ldots, p_i を処理したときに残るものの個数になっています.

時間計算量を見積もると,更新箇所の個数が

  •  1 \le i \le \pi(N^{1/4}) \sim N^{1/4} / \log N についてそれぞれ  O(N^{1/2})
  •  \pi(N^{1/4}) \lt i \le \pi(N^{1/2}) について合計で  O\left(\frac{1}{\log N} \int_{N^{1/4}}^{N^{1/2}} \frac{N}{x^2} dx\right) = O(N^{3/4} / \log N)

となり (素数の密度についての定理を用いました) 全体で  O(N^{3/4} / \log N) 時間となります.これで  100 点がとれます.

なお,素数の個数  \pi の計算については,より高速なアルゴリズムも知られています.

統計情報

45 点:1 チーム

100 点:team_2019 さん (29:26) はじめ 7 チーム

コメント

実は冒頭のストーリーは結構実話に近く,D 問題を提案しようとしたら書き間違えて,わたしが気づかないまま snuke さんが解いてくれて答えの大きさを見て気づいてわたしも解きました.高速素数カウントは初めて実装したので勉強になりました!