【笔记】莫比乌斯反演学习笔记

Author Avatar
Sakits 4月 03, 2018

莫比乌斯函数

定义

  莫比乌斯函数写作μ(d)\mu(d),定义如下:

μ(d)={1(d=1)(1)k(d=p1p2...pk)0otherwise\mu(d) = \begin{cases} 1 &(d=1) \\ (-1)^k &(d=p_1p_2...p_k) \\ 0& otherwise \end{cases}

性质

性质1

  对任何正整数nn有:

dnμ(d)={1(n=1)0(n>1)\sum_{d|n}\mu(d) = \begin{cases} 1 &(n=1) \\ 0 &(n>1) \end{cases}

  证明:
    1.当n=1n=1时,上式为μ(1)=1\mu(1)=1
    2.当n1n\neq 1时,n=p1a1p2a2...pkakn=p_1^{a_1}p_2^{a_2}...p_k^{a_k},只有质因子次数都为11的因子μ(d)0\mu(d)\neq 0,质因子有rr个的因子个数为(kr)\binom{k}{r},则有:

dnμ(d)=i=0k(ki)(1)i=i=0k(ki)(1)ki(1)i=i=0k(11)i=0\begin{aligned} \sum_{d|n}\mu(d)&=\sum_{i=0}^k\binom{k}{i}(-1)^i\\ &=\sum_{i=0}^k\binom{k}{i}(1)^{k-i}(-1)^i\\ &=\sum_{i=0}^k(1-1)^i\\ &=0 \end{aligned}

    得证

性质2

  对任何正整数nn有:

dnμ(d)d=φ(n)n\sum_{d|n}\frac{\mu(d)}{d}=\frac{\varphi(n)}{n}

  证明需要用到莫比乌斯反演的知识,下文会详细介绍。
  这里提供正反两种证明方法。
  证明11

n=i=1ndn[(i,n)=d]=dni=1n[(i,n)=d]=dni=1nd[(i,nd)=1]=dni=1d[(i,d)=1]=dnφ(d)\begin{aligned} n&=\sum_{i=1}^n\sum_{d|n}[(i,n)=d]\\ &=\sum_{d|n}\sum_{i=1}^n[(i,n)=d]\\ &=\sum_{d|n}\sum_{i=1}^{\frac{n}{d}}[(i, \frac{n}{d})=1]\\ &=\sum_{d|n}\sum_{i=1}^d[(i,d)=1]\\ &=\sum_{d|n}\varphi(d) \end{aligned}

  令F(n)=nF(n)=nf(n)f(n)φ(n)\varphi(n),代入莫比乌斯反演的式子即可得证。
  证明22

dnφ(d)=dni=1d[(i,d)=1]=dni=1dμ(i)n=n\begin{aligned} \sum_{d|n}\varphi(d)&=\sum_{d|n}\sum_{i=1}^{d}[(i,d)=1]\\ &=\sum_{d|n}\sum_{i=1}^{d}\mu(i)n\\ &=n \end{aligned}

  从第二步到第三步由性质11可得。

性质3

  μ(d)\mu(d)是积性函数,易证
  积性函数的前缀和也为积性函数

莫比乌斯函数筛

  根据性质33:莫比乌斯函数是积性函数,我们可以使用线性筛来求得莫比乌斯函数的值。

代码

inline void getmu(int n)
{
    mu[1]=1;
    for(int i=2;i<=n;i++)
    {
        if(!v[i]) mu[i]=-1, pri[++cntp]=i;
        for(int j=1;pri[j]*i<=n;j++)
        {
            v[pri[j]*i]=1;
            if(i%pri[j]==0) 
            {
                mu[pri[j]*i]=0;
                break;
            }
            mu[pri[j]*i]=-mu[i];
        }
    }
} 

莫比乌斯反演定理

  设函数F(n)F(n)f(n)f(n)满足:

F(n)=dnf(d)F(n)=\sum_{d|n}f(d)

莫比乌斯反演定理形式一:

F(n)=dnf(d)f(n)=dnμ(d)F(nd)F(n)=\sum_{d|n}f(d)\Rightarrow f(n)=\sum_{d|n}\mu(d)F(\frac{n}{d})

证明

f(n)=dnμ(d)F(nd)=dnμ(d)kndf(k)=knf(k)dnkμ(d)=f(n)\begin{aligned} f(n)&=\sum_{d|n}\mu(d)F(\frac{n}{d})\\ &=\sum_{d|n}\mu(d)\sum_{k|\frac{n}{d}}f(k)\\ &=\sum_{k|n}f(k)\sum_{d|\frac{n}{k}}\mu(d)\\ &=f(n) \end{aligned}

  第三到第四步由性质11可得。

莫比乌斯反演定理形式二:

F(n)=ndf(d)f(n)=ndμ(dn)F(d)F(n)=\sum_{n|d}f(d)\Rightarrow f(n)=\sum_{n|d}\mu(\frac{d}{n})F(d)

证明

f(n)=k=1+μ(k)kntf(t)=ntf(t)ktnμ(k)=f(n)\begin{aligned} f(n)&=\sum_{k=1}^{+\infty }\mu(k)\sum_{kn|t}f(t)\\ &=\sum_{n|t}f(t)\sum_{k|\frac{t}{n}}\mu(k)\\ &=f(n) \end{aligned}

  同理第二步到第三步由性质11可得。

例题

  11.bzoj2301: [HAOI2011]Problem b
  22.bzoj3529: [Sdoi2014]数表

一些技巧与注意事项

  1.1.仔细确定上界
  2.2.枚举gcdgcd
  3.[(i,j)=1]>x(i,j)μ(x)3.[(i,j)=1]->\sum_{x|(i,j)}\mu(x),然后将μ\mu提前
  4.4.换元
  5.φ(n)=dnμ(nd)d5.\varphi(n)=\sum_{d|n}\mu(\frac{n}{d})d
  6.dnφ(d)=n6.\sum_{d|n}\varphi(d)=n