euler_phi_table

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

std::vector<int> euler_phi_table(int n);

概要

オイラーのトーシェント関数 $\varphi(1), \ldots, \varphi(n)$

$\varphi(p^k) = p^k - p^{k-1}$。

計算量

• $O(n)$

関連項目

• multiplicative_table — 乗法的関数の値を線形篩で一括計算する
• 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 双曲線法）
• totient_sum — $\sum_{i=1}^{n} \varphi(i)$ を $O(n^{2/3})$ で計算する
• mobius_sum — メルテンス関数 $\sum_{i=1}^{n} \mu(i)$ を $O(n^{2/3})$ で計算する