积性函数

• 积性函数（数论函数，即定义域为正整数集或其子集的函数）定义
  • 当\(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)\)为容斥系数