浅谈莫比乌斯反演

2022-09-16 14:31:23 浏览数 (3)

浅谈莫比乌斯反演

那些各种各样的性质与定理,大多是前人几年甚至几十年才得出来的,哪里是你几天就能理解并证明的。

简介

莫比乌斯反演是数论中的重要内容。对于一些函数 f(n)，如果很难直接求出它的值，而容易求出其倍数和或约数和 g(n)，那么可以通过莫比乌斯反演简化运算，求得 f(n) 的值。 --OI Wiki

莫比乌斯函数

定义

mu(d)=begin{cases}1&d=1\(-1)^k&d=prod_{i=1}^kp_itext{且}p_itext{为互不相同的质数}\0&dtext{含有平方因子}end{cases}

令 n=prod_{i=1}^k p_i^{c_i}，其中 p_i 为质因子，c_ige 1。

  1. 当 n=1 时，mu(n)=1。
  2. 当 nnot = 1 时：
  • 若 exists iin[1,k],c_i>1mu(n)=1。
  • 若 forall i in [1,k],c_i=1，那么 mu(n)=(-1)^k。

性质

莫比乌斯函数是积性函数，并且有以下性质：

sumlimits_{dn}mu(d)=begin{cases}1 & n=1\0 & nnot = 1end{cases}
sumlimits_{dn}frac{mu(d)}{d}=frac{phi(n)}{n}

求法

由于莫比乌斯函数是典型的积性函数，所以也可以用欧拉筛筛出来。

代码语言：javascript复制
I void GM(){
    RI i,j;for(mu[1]=1,i=2;i<N;i  ) for(!v[i]&&(mu[p[  tot]=i]=-1,0),j=1;j<=tot&&i*p[j]<N;j  )
    if(v[i*p[j]]=1,i%p[j]) mu[i*p[j]]=-mu[i];else break ;
    for(i=1;i<N;i  ) mu[i] =mu[i-1];
}

莫比乌斯反演

为定义在非负整数域上的两个函数，且他们之间满足

F(n)=sumlimits_{dn}f(d)

。

那么我们有

f(n)=sumlimits_{dn}mu(d)F(lfloor frac{n}{d}rfloor)

这就是莫比乌斯反演定理，它还有另外一种形式：

如果

F(n)=sumlimits_{nd}f(d)

那么我们有

f(n)=sumlimits_{nd}mu(frac{d}{n})F(d)

例题

基础题

  • P2522 [HAOI2011]Problem b
  • P3455 [POI2007]ZAP-Queries
  • P2257 YY的GCD

提高题

咕了

exists wiki

0 人点赞