积性函数
定义
-
若 \(f(n)\) 的定义域为正整数域，值域为复数，即 \(f:\mathbb{Z}^+\rightarrow \mathbb{C}\)，则称为 \(f(n)\) 数论函数。
-
若 \(f(n)\) 为数论函数，且 \(f(1)=1\)，对于互质的正整数 \(p,q\) 有 \(f(pq)=f(p)f(q)\) ，则称其为积性函数。
-
若 \(f(n)\) 为积性函数，且对于任意正整数 \(p,q\) 有 \(f(pq)=f(p)f(q)\) ，则称其为完全积性函数。
常见的积性函数
- \(\varepsilon(n)=[n=1]\) （完全积性）
- \(id(n)=n\) （完全积性）
- \(1(n)=1\) （完全积性）
- \(\tau(n)=\sum_{i|n}1\)
- \(\sigma(n)=\sum_{i|n}i\)
- \(\mu\)
- \(\varphi\)
狄利克雷卷积
定义
定义两个数论函数 \(f,g\) 的狄利克雷卷积为：
\[(f*g)(n)=\sum\limits_{d|n}f(d)g(\frac{n}{d})
\]
性质
- 交换律
- 结合律
- 分配率
常见的狄利克雷卷积
- \(\tau=1*1\)
- \(\sigma=id*1\)
- \(\varphi=\mu*id\)
- \(\varepsilon=\mu*1\)
杜教筛
简介
\(\Theta(n^{\frac{2}{3}})\) 的时间内求出特定积性函数 \(f\) 的前缀和：
\[S(n)=\sum\limits_{i=1}^nf(i)
\]
要求：可以找到一个积性函数 \(g\) 使得 \((f*g)\) 的前缀和与 \(g\) 的前缀和易于计算。
主过程
\[\begin{aligned}
&\sum\limits_{i=1}^n\sum\limits_{j|i}f(\frac{i}{j})g(j) =&\sum\limits_{j=1}^n\sum\limits_{i=1}^{\lfloor\frac{n}{j}\rfloor}g(j)f(\frac{ij}{j}) =&\sum\limits_{j=1}^ng(j)\sum\limits_{i=1}^{\lfloor\frac{n}{j}\rfloor}f(i) =&\sum\limits_{j=1}^ng(j)S(\lfloor\frac{n}{i}\rfloor) \end{aligned}
\]
\[\implies g(1)S(n)=\sum\limits_{i=1}^n(f*g)(i)-\sum\limits_{i=2}^n g(i)S(\lfloor\frac{n}{i}\rfloor)
\]
递归计算，利用hash记忆化。
复杂度
直接递归的复杂度为 \(\Theta(n^{\frac{3}{4}})\) 。
若可以线性筛出 \(f\) 在 \(n^{\frac{2}{3}}\) 内的前缀和复杂度为 \(\Theta(n^{\frac{2}{3}})\) 。
证明待补。
题单
\[\begin{aligned}
1&=\sum\limits_{i=1}^{n}\sum\limits_{j|i}\mu(j) \&=\sum\limits_{j=1}^nS(\lfloor\frac{n}{j}\rfloor)
\end{aligned}
\]
\[\implies S(n)=1-\sum\limits_{j=2}^nS(\lfloor\frac{n}{j}\rfloor)
\]
参考资料：
浅谈一类积性函数的前缀和
积性函数线性筛/杜教筛/洲阁筛学习笔记
积性函数和筛子【未完结】
原文：https://www.cnblogs.com/gsjz/p/14695793.html
