mobius_table

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

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

概要

メビウス関数 $\mu(1), \ldots, \mu(n)$

$\mu(p) = -1$、$\mu(p^k) = 0$（$k \ge 2$）。

計算量

• $O(n)$

関連項目

• multiplicative_table — 乗法的関数の値を線形篩で一括計算する
• euler_phi_table — オイラーのトーシェント関数 $\varphi(1), \ldots, \varphi(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})$ で計算する