数論関数の篩法
杜教篩
数論関数 \(f(n)\) の累積和 \(F(n)=\sum_{i=1}^n f(i)\) を求めるとします。ここで、以下の条件を満たす積性関数 \(g(n)\) が存在する場合:
\(g(n)\) の累積和 \(G(n)=\sum_{i=1}^n g(i)\) が効率的に計算可能
ディリクレ積 \(h = f \ast g\) の累積和 \(H(n)=\sum_{i=1}^n h(i)\) が効率的に計算可能
以下の関係式が導出されます:
\[\begin{aligned}
\sum_{ ...
7月30日 00:10 投稿