狄利克雷卷积与莫比乌斯反演

- 概念引入

  - 数论函数

    指定义域为正整数的函数
    定义其加法为逐项相加,即$(f + g)(n) = f(n) + g(n)$
    定义其数乘为逐项相乘,即$(xf)(n) = x × f(n)$


  - 单位元

    单位元是集合中一种特别的元素,当单位元与其它元素相结合时,不会改变其它元素的值

  - 逆元

    逆元是指可以取消另一给定元素运算的元素,即将其变回单位元

  - 符号表示

    $[A]$表示条件$A$是否为真
    此处的符号"$*$"表示狄利克雷卷积

- 狄利克雷卷积

  令$t(n) = f(n) * g(n)$,则
  

$t(n) = sumlimits_{i | n} f(i)g(frac{n}{i})$


  那么狄利克雷卷积显然有下面几个性质:
    - 满足乘法交换律、结合律、分配律
    - 对于单位元$epsilon(n) = [n = 1]$,满足$epsilon(n)*f(n) = f(n)$
    - 对于每一个$f(1) e 1$的数论函数$f(n)$,皆存在其逆元$f^{- 1}(n)$,满足$f(n) * f^{- 1}(n) = epsilon(n)$,那么对于这个结论,可以令$f^{- 1}(n) = frac{1}{f(1)}left(epsilon(n) - sumlimits_{i | n, i e 1} f(i)f^{- 1}(frac{n}{i}) ight)$,再代回原式,满足条件

- 狄利克雷卷积与积性函数

  - 积性函数

    积性函数满足当$(n, m) = 1$,有$f(nm) = f(n)f(m)$

  - 相关性质

    - 若$(n, m) = 1, d | nm$,则必定存在$a | n, b | m$且满足$ab = d$,证明显然
    - 若$(n, m) = 1, a | n, b | m$,则有$(a, b) = 1$,证明显然
  这样的话,就有性质:两个积性函数的狄利克雷卷积仍是积性函数,证明:
  若$(n, m) = 1$,则有
    

$t(nm) = sumlimits_{i | nm} f(i)g(frac{nm}{i})$
$ = sumlimits_{a | n, b | m} f(ab)g(frac{nm}{ab})$
$ = sumlimits_{a | n, b | m} f(a)f(b)g(frac{n}{a})g(frac{m}{b})$
$ = t(n) * t(m)$

  另外一个性质,就是两个积性函数的逆元仍是积性函数,是用数学归纳法证明:
    令$(n, m) = 1$,当$nm = 1$时,结论显然成立
    当$nm > 1$且$n_1m_1 < nm$时$n_1m_1$结论成立,再假设$nm$时结论成立,则有(注意,积性函数中一定满足$f(1) = 1$)

$egin{aligned} f^{- 1}(nm) &= - sumlimits_{i | nm, i e 1} f(i)f^{- 1}(frac{nm}{i}) \ &= - sumlimits_{a | n, b | m, ab e 1} f(a)f(b)f^{- 1}(frac{n}{a})f^{- 1}(frac{m}{b}) \ &= f(1)f(1)f^{- 1}(n)f^{- 1}(m) - sumlimits_{a | n, b | m, ab e 1} f(a)f(b)f^{- 1}(frac{n}{a})f^{- 1}(frac{m}{b}) \ &= f^{- 1}(n)f^{- 1}(m) - epsilon(n)epsilon(m) \ &= f^{- 1}(n)f^{- 1}(m) end{aligned}$
  注:积性函数$f(1) = 1$

- 狄利克雷卷积与莫比乌斯反演

  令$mu$表示$1$在狄利克雷卷积意义下的逆元,令$g = f * 1$,则有$f = f * 1 * mu = g * mu$,再令$g(n) = sumlimits_{d | n} f(d)$,则有

$f(n) = g(n) * mu(n) = sumlimits_{d | n} g(d)mu(frac{n}{d})$

  这就是莫比乌斯反演的式子了
  那么对于函数$mu(n)$,由于$1$是积性函数,则$mu$也是积性函数,又易知(代回原式就好了)

$mu(p^k) = left{egin{aligned} 1 k = 0 \ - 1 k = 1 \ 0 k > 1 end{aligned} ight.$

  那么由积性函数,可得
  - 若$n = p_1p_2...p_k$且$p_1 e p_2 e ... e p_k$,则有

$mu(n) = (- 1)^k$

  - 若$p_k^r | n (r > 1)$,则有

$mu(n) = 0$

  那么积性筛即可

- 另附

  莫比乌斯反演的另一种形式,有

  $$g(n) = sumlimits_{n | d}f(d)$$

  则有

  $$f(n) = sumlimits_{n | d} mu(frac{d}{n})g(d)$$

原文地址:https://www.cnblogs.com/Colythme/p/9972264.html