乗法的関数累積和-中国コミュニティの方法
参考文献
ここに書いてある方法($ O(n^{2/3}(\log n)^{-1})時間)を説明する
1 疎な関数のディリクレ積
乗法的関数$ f,$ g（それぞれ適切に累積和を管理するとする）の Dirichlet 積$ fgを計算する。ただし、$ f,$ gはそれぞれ prefix の非ゼロ要素の密度が$ O((\log n)^{-1})(素数と同じオーダーかそれ以下の密度)であるとする。
$ B=n^{2/3}として$ B以下の部分は$ O(B\log B(\log B)^{-2})=O(B(\log B)^{-1})時間で畳み込める。残りはルートの上下で分けるやつで計算すると$ O(\sqrt{n}\sqrt{n/B}(\log n)^{-1})時間である。合計$ O(n^{2/3}(\log n)^{-1})時間。
2 $ n^{1/6}\lt p\leq n^{1/2}の寄与
乗法的関数の$ p冪の成分だけ取り出したものを$ f_pで表す。
$ \displaystyle \prod_{n^{1/6}\lt p\leq n^{1/2}} f_p=\exp\sum_{n^{1/6}\lt p\leq n^{1/2}}\log f_p
を利用する。$ \log f_pは形式的べき級数とみなせば簡単。$ \expは、$ \expの級数展開の$ 5次の項まで計算すればよい。
この乗法的関数の非ゼロ要素の密度は$ O((\log n)^{-1})であることがわかっている。
3 まとめる
$ \prod_{n^{1/6}\lt p\leq n^{1/2}} f_pが得られた。$ \prod_{n^{1/2}\lt p} f_pは初めから与えられているが、これを掛けるのは$ O(n^{1/2}\log n)時間でできて、$ \prod_{n^{1/6}\lt p} f_pを得る。$ p\leq n^{1/6}は工夫せず計算しても$ O(n^{2/3}(\log n)^{-1})時間になる。以上、全部合わせて$ O(n^{2/3}(\log n)^{-1})時間で計算できる。
参考文献
$ \tilde{O}(n^{1/2})時間の方法の文献を読んでくれているらしい。がんばれ～
概要
A. Dirichlet 積の計算は実は速い。
B. 素数$ pにおいて$ f(p)=0である乗法的関数を掛けるのも A と同じ計算量である。→実は非ゼロ項が$ O(n^{1/2})個なので乗法的関数を愚直に計算して Dirichlet 積を計算する。
C. log とか exp とかは、級数展開を $ \lfloor\log _2 n\rfloor次まで計算すればよい。
ーーーーーーーーーーーーーーーーーーーーーーーー
1. 累積和を計算しやすい乗法的関数$ gを用意する。ただし$ \sum_{\text{prime}\ p\leq \lfloor n/k\rfloor}g(p)から$ \sum_{\text{prime}\ p\leq \lfloor n/k\rfloor}f(p)を高速に計算できるようにしておく。
2. Bを用いて、$ g'(p)=g(p)、$ g'=\prod_{\text{prime}\ p}\exp g''_p（$ g''_pは$ g''_p(p)以外すべて$ 0の関数）なる$ g'を得る。
3. Cを用いて、$ \log g'=\sum_{\text{prime}\ p} g''_pを計算する。$ \sum_{\text{prime}\ p\leq \lfloor n/k\rfloor}g(p)の値が得られている。
4. $ \sum_{\text{prime}\ p\leq \lfloor n/k\rfloor}f(p)の値が得られる。
5. Cを用いてこれの$ \expを計算すれば、$ f'(p)=f(p)、$ f'=\prod_{\text{prime}\ p}\exp f''_p（$ f''_pは$ f''_p(p)以外すべて$ 0の関数）なる$ f'を得る。
6. Bを用いて、$ f'から$ fに変換する。
ーーーーーーーーーーーーーーーーーーーーーーーー
要は、素因数に 2 乗以上を含む成分を調整できることによって都合よく$ \sum_{\text{prime}\ p\leq \lfloor n/k\rfloor}f(p)の計算に帰着するのである。