totient_sum

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

template <class T>
T totient_sum(long long n);

概要

$\sum_{i=1}^{n} \varphi(i)$ を $O(n^{2/3})$ で計算する

$\varphi * 1 = \mathrm{Id}$（恒等関数）より $H(m) = m(m+1)/2$、$g = 1$ で杜教筛を回す。

計算量

• $O(n^{2/3})$

関連項目

• 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)$
• divisor_sum_table — 約数の総和 $\sigma_1(1), \ldots, \sigma_1(n)$
• MultiplicativeSum — 乗法的関数の累積和を劣線形で計算する（杜教筛 / Dirichlet 双曲線法）
• mobius_sum — メルテンス関数 $\sum_{i=1}^{n} \mu(i)$ を $O(n^{2/3})$ で計算する