Min25Sieve
クラス · Min_25 篩：乗法的関数の累積和を $O(N^{3/4} / \log N)$ で計算する
template <class T, class Fpe>
struct Min25Sieve;
概要
Min_25 篩：乗法的関数の累積和を $O(N^{3/4} / \log N)$ で計算する
素数 $p$ での値 $f(p)$ が $p$ の多項式 $\sum \mathrm{coef} \cdot p^{\mathrm{pw}}$ で表せる 乗法的関数 $f$ について、$S(N) = \sum_{i=1}^{N} f(i)$ を求める。素数冪での値 $f(p^e)$ は fpe で与える。
テンプレートパラメータ
| 名前 | 説明 |
|---|---|
T |
値の型（modint 等） |
Fpe |
(long long p, int e, long long pe) -> T。pe $= p^e$ で $f(p^e)$ を返す。 |
計算量
- 構築は $O(N^{3/4}/\log N)$、
sumは同じ前計算を利用して計算する
構築・破棄
| 名前 | 説明 | 計算量 |
|---|---|---|
(constructor) |
上限 n、素数項 terms、素数冪関数 fpe から構築する |
$O(N^{3/4}/\log N)$ |
メンバ関数
| 名前 | 説明 | 計算量 |
|---|---|---|
sum |
$S(N) = \sum_{i=1}^{N} f(i)$ | $O(N^{3/4}/\log N)$ |