divisor_sum_table

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

std::vector<std::int64_t> divisor_sum_table(int n);

概要

約数の総和 $\sigma_1(1), \ldots, \sigma_1(n)$

$\sigma_1(p^k) = 1 + p + \cdots + p^k$。

計算量

• $O(n)$

関連項目

• multiplicative_table — 乗法的関数の値を線形篩で一括計算する
• euler_phi_table — オイラーのトーシェント関数 $\varphi(1), \ldots, \varphi(n)$
• mobius_table — メビウス関数 $\mu(1), \ldots, \mu(n)$
• divisor_count_table — 約数の個数 $\sigma_0(1), \ldots, \sigma_0(n)$
• MultiplicativeSum — 乗法的関数の累積和を劣線形で計算する（杜教筛 / Dirichlet 双曲線法）
• totient_sum — $\sum_{i=1}^{n} \varphi(i)$ を $O(n^{2/3})$ で計算する
• mobius_sum — メルテンス関数 $\sum_{i=1}^{n} \mu(i)$ を $O(n^{2/3})$ で計算する