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)$ 個