闷声反大演

数论函数

若函数$f(n)$满足定义域为正整数域,值域为复数域,即$f$:$Z^+→C$ ,称$f(n)$为数论函数

若数论函数$f(n)$对于互质的两个正整数$p$、$q$,有$f(p⋅q)=f(p)⋅f(q)$,称$f(n)$为积性函数

若数论函数$f(n)$对于任意两个正整数$p$、$q$,有$f(p⋅q)=f(p)⋅f(q)$,称$f(n)$为完全积性函数

常见的完全积性函数

  1. 元函数 $e(n)=[n=1]$,狄利克雷卷积的乘法单位元
  2. 恒等函数 $I(n)=1$
  3. 单位函数 $id(n)=n$
  4. 幂函数 $id^k(n)=n^k$

常见的积性函数

  1. 除数函数 $\sigma_k(n)=\sum\limits_{d|n}{d^k}$
  2. 约数个数函数 $\tau(n)=\sigma_0(n)=\sum\limits_{d|n}{1}$
  3. 约数和函数 $\sigma(n)=\sigma_1(n)=\sum\limits_{d|n}{d}$
  4. 欧拉函数 $\varphi(n)=\sum\limits_{i=1}^{n}{[(n,i)=1]}$
  5. 莫比乌斯函数 对于无平方因子数$n=\prod\limits_{i=1}^{t}p_i$,$\mu(n)=(-1)^t$;对于有平方因子数$n$,$\mu(n)=0$;在狄利克雷卷积的乘法中与恒等函数互为逆元

一些性质

  • $\sum\limits_{d|n}{\mu(d)}=[n=1]$

  • $\sum\limits_{d|n}{\varphi(d)}=n$

  • $\sum\limits_{d|n}{\frac{\mu(d)}{d}}=\frac{\varphi(n)}{n}$ 此式中为分数

  • $\sum_{i=1}^{n}i\cdot[(n,i)=1]=\frac{n\varphi(n)+[n=1]}{2}$ 与n互质数的和

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

数论函数$f$和$g$的狄利克雷卷积定义为

交换律:$f \times g=g \times f$

结合律:$(f \times g) \times h=f \times (g \times h)$

单位元:$f \times e =f$

加法分配律:$f \times (g+h)=f \times g+ f\times h$

在上文数论函数的部分中提到,$\mu \times I = e$,利用这个等式可以解决下面的问题

已知$g(n)$&$g(n)=\sum\limits_{d|n}{f(d)}$,求$f(n)$

$\because $ $f \times I=\sum\limits_{d|n}{f(d)~I(\frac{n}{d})}=g$

$\therefore $ $f \times I \times \mu=g \times \mu$

即$f=\mu \times g,f(n)=\sum\limits_{d|n}{\mu(d)~ g(\frac{n}{d})} ①$

类似地,若已知$g(n)$&$g(n)=\sum\limits_{n|d}{f(d)}$

可以得到$f(n)=\sum\limits_{n|d}{\mu(\frac{d}{n}) ~ g(d)}②$

以上利用$\mu$实现$f$和$g$互相转化的过程称为莫比乌斯反演

二项式反演

分享到: