multiplicative_table
関数 · 乗法的関数の累積和を劣線形で計算する（杜教筛 / Dirichlet 双曲線法）
template <class T, class F>
std::vector<T> multiplicative_table(int n, F fpk);
概要
乗法的関数の値を線形篩で一括計算する
乗法的関数 $f$（$f(1)=1$、$\gcd(m,n)=1$ で $f(mn)=f(m)f(n)$）の $f(1), \ldots, f(n)$ を $O(n)$ で構築する。素数冪での値 $f(p^k)$ を返す callable を渡す。
テンプレートパラメータ
| 名前 | 説明 |
|---|---|
T |
値の型（modint や整数型） |
F |
(int p, int k, int pk) -> T を満たす callable。pk $= p^k$。 |
パラメータ
| 名前 | 説明 |
|---|---|
n |
上限（$n \ge 0$） |
fpk |
$f(p^k)$ を返す関数。$p$ は素数、$k \ge 1$、pk $= p^k$。 |
戻り値
f[i] $= f(i)$（$0 \le i \le n$）。f[0] = T()、f[1] = T(1)。
計算量
- $O(n)$
関連項目
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 双曲線法）totient_sum— $\sum_{i=1}^{n} \varphi(i)$ を $O(n^{2/3})$ で計算するmobius_sum— メルテンス関数 $\sum_{i=1}^{n} \mu(i)$ を $O(n^{2/3})$ で計算する