Sum of Multiplicative Function

multiplicative function $f(n)$ に対し、$F(n) := \sum_{1 \le i \le n} f(i)$ とする。ただし、ある多項式 $g$ が存在して、任意の素数 $p$ に対して $f(p) = g(p)$ とかけるとする。

このとき、$F(n)$ を時間計算量 $O(n^{2/3})$、空間計算量 $O(\sqrt{n})$ で求める。

表記

  • $\pi(n)$: $n$ 以下の素数の個数
  • $p_k$: $k$ 番目の素数(e.g. $p_1 = 2, p_2 = 3, \dots$)
  • $\mathrm{lpf}(n) :=$ ($n$ の最小素因数) (if $n \ge 2$), $\mathrm{lpf}(1) := \infty$
  • $F_\mathrm{prime}(n) := \sum_{2 \le p \le n,\,p:\,\mathrm{prime}} f(p)$
  • $F_k(n) := \sum_{i=1}^n [\mathrm{lpf}(i) \ge p_k] \cdot f(i)$
  • $V(f, n) := \{ (i, f(i)) \mid 1 \le i \le \left\lfloor \sqrt{n} \right\rfloor \} \cup \{ (\left\lfloor n/i \right\rfloor, f(\left\lfloor n/i \right\rfloor)) \mid 1 \le i \le \left\lfloor \sqrt{n} \right\rfloor \}$ (便宜上の表記)

知られた手法

  • 洲阁筛: $O(n^{3/4}/\log(n))$ time, $O(\sqrt{n})$ space.

計算方法

以下の順で示す。

  1. $V(F_\mathrm{prime}, n)$ は $O(n^{2/3})$ 時間で計算可能
  2. $V(F_\mathrm{prime}, n)$ を用いて、$V(F_{\pi(\sqrt[3]{n})+1}, n)$ は $O(n^{2/3}/\log(n))$ で計算可能
  3. $V(F_{\pi(\sqrt[3]{n})+1}, n)$ を用いて、$V(F_{\pi(\sqrt[6]{n})+1}, n)$ は $O(n^{2/3})$ で計算可能
  4. $V(F_{\pi(\sqrt[6]{n})+1}, n)$ を用いて、$V(F_{1}, n)$ は $O(n^{2/3}/\log(n))$ で計算可能

$V(F_\mathrm{prime}, n)$ の計算

省略する。(以下と同様の区間で処理を分割し、適切に fenwick tree を用いれば $O(n^{2/3})$ 時間で計算できる。)
(おそらく、$O(n^{2/3}/\sqrt[3]{\log(n)})$ でも計算できる (?) )

$V(F_{\pi(\sqrt[3]{n})+1}, n)$ の計算

$q := p_{\pi(\sqrt[3]{n})+1}$ とおく。ここで、$q > \sqrt[3]{n}$ である。

このとき、$F_{{\pi(\sqrt[3]{n})+1}}(m)$ の値は、$m$ の範囲によって以下のように計算できる:

  • $q^2 \le m \le n$ の場合: $$\begin{aligned} F_{{\pi(\sqrt[3]{n})+1}}(m) &= 1 \\ &+ (F_\mathrm{prime}(m) - F_\mathrm{prime}(q-1)) \\ &+ \sum_{q \le p \le \sqrt{m}} \left(f(p^2) + f(p) \cdot (F_\mathrm{prime}(m/p) - F_\mathrm{prime}(p)) \right)\end{aligned}$$ であり、$O(\pi(\sqrt{m}))$ で計算できる。
  • $q \le m < q^2$ の場合: $F_{{\pi(\sqrt[3]{n})+1}}(m) = 1 + (F_\mathrm{prime}(m) - F_\mathrm{prime}(p-1))$ により $O(1)$ で計算できる。
  • $1 \le m < q$ の場合: $F_{{\pi(\sqrt[3]{n})+1}}(m) = 1$ となる。

よって、$V(F_{\pi(\sqrt[3]{n})+1}, n)$ は $O\left(\left(\sum_{1 \le i \le \sqrt[3]{n}} \pi(\sqrt{n/i})\right) + \sqrt{n} + \sqrt{n}\right) = O(n^{2/3}/\log(n))$ 時間で計算できる。

$V(F_{\pi(\sqrt[6]{n})+1}, n)$ の計算

$v := \left\lfloor\sqrt[3]{n}\right\rfloor$ とおく。

このとき各 $k = \pi(\sqrt[3]{n}), \dots, \pi(\sqrt[6]{n})+1$ について、 $V(F_k, n)$ は以下のように計算できる:

  • $\{ (\left\lfloor n/i \right\rfloor, F_k(\left\lfloor n/i \right\rfloor) \mid 1 \le i \le v\}$ については、$F_{k}(m) = \sum_{e=0} f(p_k^e) \cdot F_{k+1}(m/p_k^e)$ によって計算し、$n/p_k^e \le n/(v+1)$ なる $F_{k+1}(n/p_k^e)$ については fenwick tree の query を用いて取得する。
  • $\{ (i, F_k(i)) \mid 1 \le i \le \sqrt{n}\} \cup \{ (\left\lfloor n/i \right\rfloor, F_k(\left\lfloor n/i \right\rfloor) \mid v+1 \le i \le \sqrt{n}\}$ については、fenwick tree の update を用いて更新する。

全体としての fenwick tree の update, query の回数は以下のようになる。

  • update の回数: $\mathrm{lpf}(m) > \sqrt[6]{n}$ を満たすような正の整数 $m$ ($m \le n/(v+1)$) は $O(n^{2/3}/\log{n})$ 個しか存在しない(cf. https://en.wikipedia.org/wiki/Buchstab_function)ため、$O(n^{2/3}/\log(n))$ 回となる。
  • query の回数: $O\left(\sum\limits_{\sqrt[6]{n} < p \le \sqrt[3]{n}} \left(\sum\limits_{i=1}^v \log_{p}(n/i)\right)\right) = O( (\sqrt[3]{n}/\log(n)) \cdot \sqrt[3]{n}) = O(n^{2/3}/\log(n))$ 回となる。

よって、時間計算量は $O(n^{2/3}/\log(n) \cdot \log(n)) = O(n^{2/3})$ となる。

また、fenwick tree の update の際に列挙する $p_k$-rough number の最大素因数は $\sqrt{n}$ 未満となるため、($\sqrt{n}$ 以下の素数を所持しているだけでよく、)空間計算量も $O(\sqrt{n})$ で抑えられる。

$V(F_1, n)$ の計算

$F_{k}(m) = \sum_{e=0} f(p_k^e) \cdot F_{k+1}(m/p_k^e)$ を用いて、$k = \pi(\sqrt[6]{n}), \dots, 1$ の順に $V(k, n)$ を更新すればよい。

$V(F_k, n)$ の計算量は $O\left(\sum_{i=1}^{\sqrt{n}}(\log_{p_k}(n/i) + \log_{p_k}(i)) \right)$ となり、全体としての時間計算量は $O\left(\sum_{2 \le p \le \sqrt[6]{n}} \sum_{i=1}^{\sqrt{n}}\left(\log_{p}(n/i) + \log_{p}(i)\right) \right) = O(n^{2/3}/\log(n))$ となる。

以上により、$F(n) = F_1(n)$ は時間計算量 $O(n^{2/3})$、空間計算量 $O(\sqrt{n})$ で計算できる。

実装

(省略)

関連資料

その他

  • $\{ F(i) \mid 1 \le i \le \lfloor\sqrt[3]{n}\rfloor \} \cup \{ F(\lfloor\sqrt{n/i}\rfloor) \mid 1 \le i \le \lfloor\sqrt[3]{n}\rfloor \}$ も $O(n^{2/5})$ time, $O(n^{1/3})$ space で計算できる。
    • $\sqrt[3]{n}, \sqrt[6]{n}$ の部分を、順に $\sqrt[5]{n}, \sqrt[15]{n}$ と変更すればよい。
    • これは、$\sum_{i=1}^{\lfloor \sqrt{n} \rfloor} f(i) \cdot G(\left\lfloor n/i^2 \right\rfloor)$ の計算の高速化に使える。