莫比乌斯函数与狄利克雷卷积

• 积性函数

  • 积性函数（数论函数，即定义域为正整数集或其子集的函数）定义
    • 当\(f(n)=f(a)*f(b)\)对 任意\(a*b=n且gcd(a,b)=1\)成立时，我们称\(f(x)\)为积性函数
    • 特别的，当\(f(n)=f(a)*f(b)\)对 任意\(a*b=n且不要求a,b互质\)成立时，我们称\(f(n)\)为完全积性函数
  • 一些常见的积性函数
    • 元函数 \(e(x)=[x==1]\)
    • 不变函数 \(I(x)=1\)
    • 单位函数 \(id(x)=x\)
    • 欧拉函数 \(\varphi(x)=[1,x]中与x互质的数的个数\)
    • 莫比乌斯函数 \(\mu(x)=\begin{cases}1,x==1\\(-1)^k,x=\prod_{i=1}^kp_i\\0,x=\prod_{i=1}^kp_i^{r_i}且\exist r_i>1\end{cases}\)
  • 当我们把 积性函数定义 看\(N\)遍后，我们不难发现 在上述积性函数中
    • 是完全积性函数的是：
      • 元函数 \(e(x)\)
      • 不变函数 \(I(x)\)
      • 单位函数 \(id(x)\)
    • 是积性函数的是：
      • 欧拉函数 \(\varphi(x)\)
      • 莫比乌斯函数 \(\mu(x)\)

• 狄利克雷卷积

  • 狄利克雷卷积定义

    • \(f(x),g(x)\)为积性函数，\(\sum_{d|n}f(d)*g(\frac{n}{d})\)表示将\(f(x)\)与\(g(x)\)狄利克雷卷积。
    • 狄利克雷卷积还有一种简化表示方式\(\sum_{i*j=n}f(i)*g(j)\)

  • 狄利克雷卷积性质（为方便表述，以下我将狄利克雷卷积写成“ * ”）

    • 卷积出来的函数\(h(x)=\sum_{d|n}f(d)*g(\frac{n}{d})\)，也是积性函数

      • 证明：

      • \[ h(x)=\sum_{d|n}f(d)*g(\frac{n}{d})\设a*b=x且(a,b)=1\即证h(x)=\sum_{d_1|a}(f(d_1)*g(\frac{a}{d_1}))\cdot\sum_{d_2|b}(f(d_2)*g(\frac{b}{d_2}))\\forall d_1,d_2满足(d_1,d_2)=1\\Rightarrow h(x)=\sum_{d_1|a,d_2|b}f(d_1)*f(d_2)*g(\frac{a}{d_1})*g(\frac{b}{d_2})\\Rightarrow h(x)=\sum_{d_1|a,d_2|b}f(d_1*d_2)*g(\frac{a*b}{d_1*d_2})\记 c=d_1*d_2\\Rightarrow h(x)=\sum_{c|n}f(c)*g(\frac{n}{c}) \]

    • 交换律

      • \(f*g=g*f\)
      • \(\sum_{d|n}f(d)*g(\frac{n}{d})=\sum_{d|n}g(d)*f(\frac{n}{d})\)
        • 证明：
        • 如果这样不够显然，我们考虑狄利克雷卷积的另一简化版本
        • \(\sum_{ij=n}f(i)*g(j)=\sum_{ij=n}g(i)*f(j)\)
        • 这样应该足够显然了

    • 结合律

      • \((f*d)*g=f*(d*g)\)

        • 证明：

        • \[ Lhs=\sum_{i_1j_1=n}(\ \sum_{i_2j_2=i_1}f(i_2)*d(j_1)\ )*g(j_1)\=\sum_{i_1j_1=n}(\ \sum_{i_2j_2=i_1}f(i_2)*d(j_2)*g(j_1)\ )\=\sum_{i_2j_2j_1=n}f(i_2)*d(j_2)*g(j_1)\Rhs=\sum_{i_1j_1=n}(\ \sum_{i_2j_2=i_1}d(i_2)*g(j_2)\ )*f(j_1)\=\sum_{i_1j_1=n}(\ \sum_{i_2j_2=i_1}d(i_2)*g(j_2)*f(j_1)\ )\=\sum_{i_2j_2j_1=n}d(i_2)*g(j_2)*f(j_1)\\]

        • 注意到\((i_2,j_2,j_1)=1\)，因此相当于是将\(n\)分为三部分相乘，这个式子是轮换对称式，因此\(Lhs=Rhs\)

    • 分配律

      • \((f+d)*g=f*g+d*g?\)

        • 证明：

        • \[ \sum_{x|n}(\ (f(x)+d(x))*g(\frac{n}{x})\ )\=\sum_{x|n}(\ f(x)*g(\frac{n}{x})+d(x)*g(\frac{n}{x})\ )\=\sum_{x|n}f(x)*g(\frac{n}{x})+\sum_{x|n}d(x)*g(\frac{n}{x}) \]

  • 狄利克雷卷积 结合 常用积性函数 的几个常用公式

    • \(\sum_{d|n}\varphi(d)=id(n)\)，即\(\varphi*I=id\)
    • \(\sum_{d|n}\mu(d)=e(n)\)，即\(\mu*I=e\)

• 莫比乌斯反演

  • 莫比乌斯函数的一个重要性质已在上文中出现过，即\(\mu*I=e\)。以下的多数说明中都将使用该公式，请各位牢记

  • 莫比乌斯反演\(1\)

    • 当我们有\(f(x),g(x)\)为积性函数时，\(f(n)=\sum_{d|n}g(d)\)

    • 对该式进行 莫比乌斯反演 后，得\(g(n)=\sum_{d|n}\mu(d)*f(\frac{n}{d})\)

      • 证明：

      • \[ f=g*I\f*\mu=g*I*\mu\f*\mu=g*e\g(n)=f*\mu\即 g(n)=\sum_{d|n}f(d)*\mu(\frac{n}{d})\或 g(n)=\sum_{d|n}\mu(d)*f(\frac{n}{d}) \]

  • 莫比乌斯反演\(2\)

    • 当我们有\(f(x),g(x)\)为积性函数时，\(f(n)=\sum_{n|d}g(d)\)
    • 对该式进行 莫比乌斯反演 后，得\(g(n)=\sum_{n|d}\mu(\frac{d}{n})*f(d)\)
    • 证明与上面 莫比乌斯反演\(1\) 类同

  • 莫比乌斯反演理解

    • 不难发现，当我们能够较为方便的求解\(f(n)\)的值且我们想要得到\(g(n)\)的值的时候，我们利用 莫比乌斯反演 能够较为快速的获得\(g(n)\)
    • 其次，其实莫比乌斯函数实质上是容斥系数，而从\(f\)反推\(g\)的过程则可以看成容斥的过程
      • 我们将\(f(n)\)看成包含\(n\)所有约数的集合，而\(g(d)\)则是仅包含\(d\)的集合
      • 反演后的式子的含义我们可以看成 \(\mu(d)\)为容斥系数

• 常见积性函数的求法

莫比乌斯函数与狄利克雷卷积

原文：https://www.cnblogs.com/shjrd-dlb/p/10780995.html