Sum of Multiplicative Function on Powerful Numbers

multiplicative function $f(n)$ に対し、$F(n) := \sum\limits_{m: \text{ powerful number}} f(m)$ とする。ただし、ある多項式 $g$ が存在して、任意の素数 $p$ に対して $f(p^2) = g(p)$ とかけるとする。

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

続きを読む

格子点の数え上げの高速化

凸関数・凹関数で囲まれる範囲の格子点の個数の数え上げなどを、凸包を用いて高速化するテクニックです。

半径 $n$ の円に含まれる格子点の個数を $O(n^{2/3})$ ほど、$1$ から $n$ までの約数の総和を $O(n^{1/3} \log{(n)})$ ほどで求めることができます。

続きを読む