MultiplicativeSum

クラス · 乗法的関数の累積和を劣線形で計算する（杜教筛 / Dirichlet 双曲線法）

template <class T, class Gsum, class Hsum>
struct MultiplicativeSum;

概要

乗法的関数の累積和を劣線形で計算する（杜教筛 / Dirichlet 双曲線法）

乗法的関数 $f$ の累積和 $S(n) = \sum_{i=1}^{n} f(i)$ を $O(n^{2/3})$ で求める。 $f$ とディリクレ畳み込み $f * g$ がともに累積和を計算しやすい $g$ を選び、恒等式 $\sum_{i=1}^{m} (f * g)(i) = \sum_{d=1}^{m} g(d) S(\lfloor m/d \rfloor)$ から $g(1) S(m) = H(m) - \sum_{d=2}^{m} g(d) S(\lfloor m/d \rfloor)$ を再帰的に解く。

テンプレートパラメータ

名前	説明
`T`	値の型（modint や整数型）
`Gsum`	`(long long m) -> T`。$G(m) = \sum_{i=1}^{m} g(i)$。
`Hsum`	`(long long m) -> T`。$H(m) = \sum_{i=1}^{m} (f * g)(i)$。

計算量

推奨閾値では構築 $O(n^{2/3})$、問合せ $O(1)$

構築・破棄

名前	説明	計算量
`(constructor)`	累積和の小さい値と Dirichlet 畳み込みの累積和から構築する	`threshold` を $B$ として $O(B + n/\sqrt B)$、$B \approx n^{2/3}$ で $O(n^{2/3})$

メンバ関数

名前	説明	計算量
`sum`	$S(n) = \sum_{i=1}^{n} f(i)$	$O(1)$
`get`	$S(m) = \sum_{i=1}^{m} f(i)$（$m \le n$、$\lfloor n/i \rfloor$ の形の値）	$O(1)$

メンバの詳細

(constructor)

MultiplicativeSum(long long n, std::vector<T> f_prefix, T g1, Gsum G, Hsum H);

累積和の小さい値と Dirichlet 畳み込みの累積和から構築する

パラメータ n: 上限
パラメータ f_prefix: $f$ の累積和。f_prefix[k] $= \sum_{i=1}^{k} f(i)$（$k \le$ threshold）。 threshold は $n^{2/3}$ 程度を推奨（base case の打ち切り）。
パラメータ g1: $g(1)$（多くの場合 $1$）
パラメータ G: $G(m) = \sum_{i=1}^{m} g(i)$
パラメータ H: $H(m) = \sum_{i=1}^{m} (f * g)(i)$
計算量: threshold を $B$ として $O(B + n/\sqrt B)$、$B \approx n^{2/3}$ で $O(n^{2/3})$