感觉这次省选讲课里好像只有洲爷的课正常，于是就来写一写
积性函数
积性函数：$\forall a,b \in N^+,\ gcd(a,b)=1,\ f(a\cdot b)=f(a)\cdot f(b)$
一些常见的积性函数:
欧拉函数：
- $\varphi(n)$表示$n$以内与$n$互质的数的个数。
- 设$n=p_1^{q_1}\cdot p_2^{q_2}\ldots p_k^{q_k}$,$\varphi(n)=n\cdot \Pi_{i=1}^{k} \frac {p_i-1}{p_i}$
莫比乌斯函数：
- 如果$n$有平方因子，则$\mu (n)=0$
- 如果$n$没有平方因子，则设$n=p_1^{q_1}\cdot p_2^{q_2}\ldots p_k^{q_k}$，$\mu (n)=(-1)^k$
除数函数：
- $\sigma _k(n)$表示$n$的所有正因子的$k$次幂的和。
- 特别的
- $d(n)=\sigma _0(n)$表示$n$的正因子个数。
- $\sigma(n)=\sigma_1(n)$表示$n$的所有正因子之和。
最大公因数函数：
- $gcd(n,k)$在$k$为固定时，$n,k$的最大公因数。
完全积性函数：$\forall a,b \in N^+\ ,f(a\cdot b)=f(a)\cdot f(b)$
一些常见的完全积性函数：
幂函数：
- $ld_k(n)=n^k$
- 特别的
- $1(n)=ld_0(n)=1$
- $ld(n)=ld_1(n)=n$
单位函数：
- $\rm e(n)=\epsilon (n)=\begin{cases}1 & n=1 \\0 & n>1\end{cases}$
积性函数的一些性质
性质一：
- 设$n=p_1^{q_1}\cdot p_2^{q_2}\ldots p_k^{q_k}$，$f(n)=\Sigma_{i=1}^{k} f(p_i^{q_i})$
- 所以如果可以快速求出$f(p_k^{q_k})$的值，就可以用Euler筛法$O(n)$求出所有$f(i)(i\leq n)$的值。
性质二：
- 若$f，g$为积性函数，那么
- 它们的点积$(f\cdot g)(i)=f(i)\cdot g(i)$也是积性函数
- 它们的商$(\frac {f}{g})(i)=\frac {f(i)}{g(i)}$也是积性函数
Back To Menu
$Dirichlet$卷积
定义：
- 两个数论函数$f,g$的$Dirichlet$卷积为：$$(f*g)(n)=\sum_{d|n} f(d)\cdot g(\frac {n}{d})$$
性质：
- 交换律：$f*g=g*f$
- 结合律：$(f*g)*h=f*(g*h)$
- 分配律：$f*(g+h)=f*g+f*h$
- 单位元：$\epsilon*f=f$
- 若$f,g$为积性函数，则$f*g$也为积性函数
一些常见的$Dirichlet$卷积：
- $d(n)=\sum_{d|n} 1\Leftrightarrow d=1*1$
- $\sigma(n)=\sum_{d|n} d\Leftrightarrow \sigma=1*ld$
- $\epsilon(n)=\sum_{d|n}\mu(d)\Leftrightarrow \epsilon=1*\mu$
- $\varphi(n)=\sum_{d|n}\mu(d)\cdot \frac {n}{d} \Leftrightarrow \varphi=\mu*ld$
- $n=\sum_{d|n}\varphi(d)\Leftrightarrow ld=1*\varphi$
Back To Menu
莫比乌斯反演
莫比乌斯反演公式：
- 如果两个数论函数$f,g$满足$$f(n)=\sum_{d|n}g(d)$$
- 则它们满足$$g(n)=\sum_{d|n}\mu(d)\cdot f(\frac{n}{d})$$
- 反之亦然
- 写成$Dirichlet$卷积形式为$f=g*1\Leftrightarrow g=\mu*f$
证明：
- 设，$f=g*1$
- 两边都卷上，$\mu$,得$\mu*f=\mu*g*1$
- 整理得，$\mu*f=\epsilon*g=g$
- 两边都卷上1，$g*1=\mu*f*1=\epsilon*f=f$
- 证毕
莫比乌斯等式：
- $${\rm e}(n)=\sum_{d|n}\mu(d)$$
- 设$$n=\sum_{i=1}^{k} p_i^{q_i}，\ n’=\sum_{i=1}^{k}p_i，\ S=\lbrace 1,2,\ldots ,k\rbrace $$
- 那么$$\sum_{d|n}\mu(d)=\sum_{d|n’}\mu(d)=\sum_{I\subseteq S}(-1)^I=\sum_{i=0}^{k}{k \choose i}(-1)^i=(1-1)^k$$
- 证毕
简单的应用：
- $$\varphi=\mu*ld\Leftrightarrow ld=\varphi*1$$
- $$\varphi(n)=\sum_{d|n}\mu(d)\cdot \frac{n}{d}\Leftrightarrow n=\sum_{d|n}\varphi(d)$$
另一种形式：
- 在整数集$D$中，$$f(x)=\sum_{x|d,d\in D}g(d)\Leftrightarrow g(x)=\sum_{x|d,d\in D}\mu(d)f(\frac{d}{x})$$
- 两种形式的本质都是容斥原理
Back To Menu
一类积性函数求前缀和问题
4.22 这个坑不知道已经在这里多久了。。(:з」∠) 。。终于要来填掉了。。
我们知道一般的积性函数可以用欧拉筛$O(n)$求值，但是在一些题目里要求在低于线性的复杂度下求积性函数的前缀和。这个时候我们就需要一种更加高效的求前缀和的算法。
现在OI圈里比较常见的方法是杜教筛，可以做到在$O(n^{\frac{3}{4}})$或$O(n^{\frac{2}{3}})$的时间内求出积性函数的前缀和。
杜教筛：
- 现在我们要求$S(n)=\sum_{i=1}^{n}f(i)$
- 我们可以找出另一个函数g，然后考虑$(g*f)(n)$的前缀和
$$
\begin{align}
&\ \sum_{i=1}^{n}(f*g)(i) \\
= &\ \sum_{i=1}^{n}\sum_{j|i}f(j)g(\frac{i}{j}) \\
= &\ \sum_{\frac{i}{j}}^{n}\sum_{j=1}^{\left\lfloor\cfrac{n}{\frac{i}{j}}\right\rfloor}f(j)g(\frac{i}{j}) \\
= &\ \sum_{i=1}^{n}g(i)\sum_{j=1}^{\lfloor\frac{n}{i}\rfloor}f(j) \\
= &\ \sum_{i=1}^{n}g(i)S(\lfloor\frac{n}{i}\rfloor) \\
\end{align}$$
- 然后我们就可以得到一个关于$S(n)$的递推式$$g(1)S(n)=\sum_{i=1}^{n}(f*g)(i)-\sum_{i=2}^{n}g(i)S(\lfloor\frac{n}{i}\rfloor)$$
- 所以如果我们可以快速的求出$g$和$(f*g)$的前缀和，那就可以用记忆化搜索做到$O(n^{\frac{3}{4}})$的复杂度。如果原函数也可以快速求前缀和，那我们可以预处理$\sqrt{n}$以内的结果，这样就可以做到$O(n^{\frac{2}{3}})$的复杂度.
- 现在我们已经可以很轻松的求出简单的积性函数如$\varphi\ \mu$的前缀和了
- 但是对于一些比较复杂的函数，想要找一个合适的g是比较困难的。对于较复杂的函数一般有两个比较基本的形式
- 求$S(n)=\sum_{i=1}^{n}(f*g)(i)$的值，$g(i)$为完全积性函数，这时有$$S(n)=\sum_{i=1}^{n}[(f*1)\cdot g](i)-\sum_{i=2}^{n}S(\lfloor\frac{n}{i}\rfloor)$$
- 求$S(n)=\sum_{i=1}^{n}(f*g)(i)$的值，这时有$$S(n)=\sum_{i=1}^{n}g(i)\sum_{ij<=n}(f*1)(j)-\sum_{i=2}^{n}S(\lfloor\frac{n}{i}\rfloor)$$
- 有了这些性质我们就可以较容易地求出积性函数的前缀和了
Back To Menu
有错误请指出$$\mathcal {FIN.}$$
