卷积与反演

狄利克雷卷积

$$(f\ast g)(n)=\sum_{d|n}f(d)g(\frac{n}{d}) （d为n的因子）$$

称为 $f(x)$ 和 $g(x)$ 在n上的卷积

有以下性质

1. $f\ast g=g\ast f$

2. $(f\ast g)\ast h=f\ast (g\ast h)$

3. $(f+g)\ast h=f\ast h + g \ast h$

4. $\mu \ast I=\varepsilon$
   （$\varepsilon(n)=[n=1]$ （仅在n=1时为1，否则为0））
   （$I(n)=1$）

5. $\varphi \ast I=id$
   （$id(n)=n$）

6. $\mu \ast id=\varphi$

其中上面的第四五个性质最为常用，我们有比较直观的形式

$$[n=1]=\sum_{d|n} \mu(d)$$

$$f(x)=\sum_{d|f(x)}\varphi(d)$$

反演

与gcd有关的问题常用莫比乌斯反演和欧拉反演

莫比乌斯反演

有判断函数常用莫比乌斯反演

$$\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)=k]$$

变形

$$\sum_{i=1}^{\left [ \frac{n}{k} \right ] } \sum_{j=1}^{\left [ \frac{m}{k} \right ] } [gcd(i,j)=1]$$

由莫比乌斯反演可得

$$\sum_{i=1}^{\left [ \frac{n}{k} \right ] } \sum_{j=1}^{\left [ \frac{m}{k} \right ] }\sum_{d|gcd(i,j)}\mu (d)$$

$d|gcd(i,j)$，则可推出 $d|i$ 且 $d|j$

所以交换求和顺序

$$\sum_{d=1}^{\left [ \frac{n}{k} \right ] }\mu (d)\sum_{i=1}^{\left [ \frac{n}{kd} \right ] } \sum_{j=1}^{\left [ \frac{m}{kd} \right ] }$$

$$\sum_{d=1}^{\left [ \frac{n}{k} \right ] }\mu (d)\left [ \frac{m}{kd} \right ] \left [ \frac{n}{kd} \right ]$$

欧拉反演

gcd求和常用欧拉反演

$$\sum_{i=1}^{n}\sum_{j=1}^{m}gcd(i,j)$$

由欧拉反演可得

$$\sum_{i=1}^{n} \sum_{j=1}^{m} \sum_{d|gcd(i,j)} \varphi (d)$$

交换求和顺序

$$\sum_{d=1}^{n} \varphi (d) \sum_{i=1}^{\left [ \frac{n}{d} \right ] } \sum_{j=1}^{\left [ \frac{m}{d} \right ] }$$

$$\sum_{d=1}^{n} \varphi (d) \left [ \frac{n}{d} \right ] \left [ \frac{m}{d} \right ]$$

杜教筛

求

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

其中 $f(i)$ 为积性函数

再找一个积性函数 $g$ ，考虑狄利克雷卷积

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

$$\sum_{i=1}^{n}\sum_{d|i}f(d)g(\frac{i}{d})$$

为了更好地处理我们有 $\frac{i}{d}=k$ 考虑主要枚举k，$k\in \left [ 1,n \right ]$；再枚举d，$d\in \left [ 1,\frac{n}{k} \right ]$，然后就有下面的变形

$$\sum_{d=1}^{n}g(d)\sum_{i=1}^{\left [ \frac{n}{d} \right ] }f(i)$$

$$\sum_{d=1}^{n}g(d)s(\left [ \frac{n}{d} \right ] )$$

然后有

$$g(1)s(n)=\sum_{i=1}^{n}g(i)s(\left [ \frac{n}{i} \right ] )-\sum_{i=2}^{n}g(i)s(\left [ \frac{n}{i} \right ] )$$

$$g(1)s(n)=\sum_{i=1}^{n}(f \ast g)(i)-\sum_{i=2}^{n}g(i)s(\left [ \frac{n}{i} \right ] )$$

选择合适的 $g$，可以消掉 $g(1)$ 并且方便地求出 $\sum_{i=1}^{n}(f \ast g)(i)$，$\sum_{i=2}^{n}g(i)$ 通过前缀和可以求出，$s(\left [ \frac{n}{i} \right ] )$可以通过数论分块+递归求出，总时间复杂度 $O(n^{\frac{3}{4}})$

例如对于 $f=\mu$ 我们可以选取 $g=I$，$f\ast g=\varepsilon$

对于 $f=\varphi$ 我们可以选取 $g=I$，$f \ast g =id$

从而达到快速求解