卷积与反演

狄利克雷卷积

(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$

从而达到快速求解