$t=f*g\\ t(n)=\sum_{d|n}^{}f(d)g(\frac{n}{d})=\sum_{ij=n}^{}f(i)g(j)$

狄利克雷卷积

$交换律f∗g=g∗f$
$结合律(fg)h=g(fh)$
$分配律(f+g)∗h=fh+gh$

数论函数

$\phi(n)$
$\mu(n)$
$id(n)=n$
$d(n)=约数个数$
$\sigma(n)=约数和$
$\epsilon(n)=[n==1]$

两个积性函数的狄利克雷卷积是积性函数。

积性函数的逆是积性函数。

根据数学知识

$\phi*1=id$
$\mu*1=\epsilon$
$\mu*d=1$
$1*1=d$
$\phi = Id * \mu$

杜教筛

求

$S(n)=\sum_{i=1}^{n} f(n)$

找到一个积性函数$g(n)$,使$f*g$好求

$\sum_{i=1}^{n}\sum_{d|n}g(d)f(\frac{n}{d})= \sum_{d=1}^{n}g(d)\sum_{i}^{id<n}f(i)= \sum_{d=1}^{n}g(d)\sum_{i=1}^{\frac{n}{d}}f(i)= \sum_{d=1}^{n}g(d)S(\frac{n}{d})\\ g(1)*S(n)=\sum_{i=1}^{n}(f*g)-\sum_{d=2}^{n}g(d)S(\frac{n}{d})$

例

$S(n)=\sum_{i=1}^{n} \phi(n)\\ S(n)=g(1)*S(n)=\sum_{i=1}^{n}(f*g)-\sum_{d=2}^{n}g(d)S(\frac{n}{d})= \sum_{i=1}^{n}i-\sum_{d=2}^{n}S(\frac{n}{d})$