杜教筛学习笔记

狄利克雷卷积

• 定义：对于函数$f(n)$和$g(n)$，$(f\ast g)(n)=\sum\limits_{d|n} f(d)g(\dfrac{n}{d})$

常见完全积性函数：

• 元函数 $\epsilon(n)=[n=1]$
• 单位函数$id(n)=n$
• 常数函数$1(n)=1$

常见卷积：

1：

• 因为$\sum\limits_{d|n}\mu(d)=[n=1]=\epsilon$
• 所以两边卷个1得到$\mu \ast 1=\epsilon$
• 然后我们可以得出$\sum\limits_{i=1}^n(1*\mu)=1$

2：

• 因为$\sum\limits_{d|n}\phi(d)=n=id(n)$
• 所以卷个1得到$\phi\ast1=id$
• 然后可以得到$\sum\limits_{i=1}^n(1*\phi)=\sum\limits_{i=1}^nid(i)=\dfrac{n\ast (n+1)}{2}$

3 :

• 因为$\phi\ast1=id$
• 两边卷个$\mu$得到$\phi * 1 * \mu=id\ast\mu$
• $\phi\ast\epsilon=id\ast\mu$
• $\phi(n)=\sum\limits_{d|n}\mu(d)\times\dfrac{n}{d}$
• 两边同除以$n$得$\dfrac{\phi(n)}{n}=\sum\limits_{d|n}\dfrac{\mu(d)}{d}$

4 :

• $\sum\limits_{i=1}^ni^k\ast\phi(i)$
• 卷上$id^k$得$\sum\limits_{d|n}d^k\phi(d)*(\dfrac{n}{d})^k=n^k$

杜教筛

其实就是一个式子：

$g(1)S(n)=\sum\limits_{i=1}^n(f\ast g)-\sum\limits_{i=2}^ng(i)S(\dfrac{n}{i})$

杜教筛用于快速求前缀和，复杂度似乎是$\Theta(n^{\frac{2}{3}})$，然而我并不会证明。

有了这个式子，我们就可以利用一个好算的卷积前缀和递归求解一个和式。

由上面的常见卷积1可得：$S(n)=\sum\limits_{i=1}^n\epsilon(i)-\sum\limits_{i=2}^nS(\dfrac{n}{i})=1-\sum\limits_{i=2}^nS(\dfrac{n}{i})$

后面那个式子显然可以整除分块。

其他的同理。

例题

• 咕