学习总结-莫比乌斯反演

· · 个人记录

（〇）前置知识

1.数论的基础知识(关于质数，约数)

2.二项式定理

3.数论分块*

4.积性函数*

5.Dirichlet卷积*

6.莫比乌斯函数*

注：带"*"号的本文会具体阐述

（一）数论分块

引理1:

\forall a,b,c\in \mathbb{Z},\lfloor{\dfrac{a}{bc}}\rfloor=\lfloor \dfrac{\lfloor\frac{a}{b}\rfloor}{c}\rfloor

这个公式比较容易理解，不详细阐述了。

略证一下:

\dfrac{a}{b}=\lfloor\dfrac{a}{b}\rfloor+r(0\leq r<1) \lfloor\dfrac{a}{bc}\rfloor=\lfloor\dfrac{a}{b}\cdot\dfrac{1}{c}\rfloor=\lfloor\dfrac{\lfloor\frac{a}{b}\rfloor}{c}+\dfrac{r}{c}\rfloor=\lfloor\dfrac{\lfloor\frac{a}{b}\rfloor}{c}\rfloor

引理2：

\forall n\in\mathbb{N_+},|\{ \lfloor\dfrac{n}{d}\rfloor|d\in\mathbb{N_+},d\leq n\}|\leq\lfloor 2 \sqrt{n}\rfloor

这个引理描述了\lfloor \dfrac{n}{d}\rfloor的解的集合大小不会超过2\sqrt{n}

容易证明。

由此，我们可以得到一个算法：数论分块。

先来看这样的一个问题：求\sum\limits_{i=1}^{n} \lfloor\dfrac{n}{i}\rfloor

如果我们枚举每个i，那么显然时间复杂度是\Theta(n)，有没有更快的算法？

根据引理2我们可以知道，对于所有\lfloor\dfrac{n}{i}\rfloor，至多只有2\sqrt{n}个不同的解。

直观感受一下:

不难发现，\lfloor\dfrac{n}{i}\rfloor的值是一段一段的(在一个连续的区间内)，而这个区间的右端点恰好是\lfloor\dfrac{n}{\lfloor\frac{n}{i}\rfloor}\rfloor的值。

证明略。代码如下:

for(int l = 1, r; l <= n; l = r+1){
    r = n/(n/l);
    f(l, r);
}

[拓展]二维数论分块

什么是二维数论分块？

举个例子，如果我们要在求\lfloor\dfrac{n}{i}\rfloor的同时求出\lfloor\dfrac{m}{i}\rfloor，这时就需要用到二维数论分块。

代码实现很简单只需要加上一行:

for(int l=1, r; l <= min(n, m); l = r+1){
    r = min(n/(n/l), m/(m/l));
    f(l, r);
}

（二）积性函数

定义

若函数f(n)满足f(1)=1且\forall x,y\in \mathbb{N_+},\gcd(x,y)=1都有f(xy)=f(x)f(y)，则f(n)为积性函数。

若函数f(n)满足f(1)=1且\forall x,y\in\mathbb{N_+}都有f(xy)=f(x)f(y)，则f(x)为完全积性函数。

性质

若f(x)和g(x)均为积性函数，则以下函数也为积性函数。

h(x)=f(x^p) h(x)=f^p(x) h(x)=f(x)g(x) h(x)=\sum\limits_{d|x}f(d)g(\dfrac{x}{d})

设x= \prod p_{i}^{k_i}其中p_i是质数

若F(x)为积性函数，则有F(x)=\prod F(p_i^{k_i})。

若F(x)为完全积性函数，则有F(x)=\prod F(p_i)^{k_i}

举例

单位函数：\varepsilon=[n=1](完全积性函数)

恒等函数：\operatorname{id}_k(n)=n^k其中\operatorname{id}_1(n)简记作\operatorname{id}(n)(完全积性函数)

常数函数：\operatorname{1}(n)=1(完全积性函数)

除数函数：\sigma_k(n)=\sum\limits_{d|n}d^k(积性函数)

欧拉函数：\varphi(n)=\sum\limits_{i=1}^{n}[\gcd(i,n)=1](积性函数)

（三）Dirichlet卷积

又称“狄利克雷卷积”。

定义

定义两个数论函数f,g的Dirichlet卷积为:

(f*g)(n)=\sum\limits_{d|n} f(d)g(\dfrac{n}{d})

性质

1.交换律：$f*g=g*f

2.结合律：(f*g)*h=f*(g*h)

3.分配律：f*(g+h)=f*g+f*h

4.f*\varepsilon=f其中\varepsilon是Dirichlet卷积的单位元

例子(公式)

\varepsilon=\mu*1\iff \varepsilon(n)=\sum \limits_{d|n}\mu(d) d=1*1\iff d(n)=\sum\limits_{d|n}1 \sigma = \operatorname{id}*1\iff \sigma(n)=\sum\limits_{d|n}d \varphi=\mu*\operatorname{id}\iff \varphi (n)=\sum\limits_{d|n}d\cdot\mu(\dfrac{n}{d})

（四）莫比乌斯函数

定义

$$\mu(n)=\begin{cases}1&n=1\\0&\exists p>1:p^2|n\\(-1)^{\omega(n)}&otherwise\end{cases}$$ 其中$\omega(n)$表示$n$的本质不同质因子个数，它也是一个积性函数。 ### 性质(敲黑板) 除了积性函数的性质以外，莫比乌斯函数还有如下性质 $$\sum\limits_{d|n}\mu(d)=\begin{cases}1&n=1\\0&n\not=1\end{cases}$$ 即 $$\sum\limits_{d|n}\mu(d)=\varepsilon(n),\mu*1=\varepsilon$$ 证明: 设$n=\prod\limits_{i=1}^{k}p_i^{c_i},n'=\prod\limits_{i=1}^kp_i

那么\sum\limits_{d|n}^k\mu(d)=\sum\limits_{d|n'}^k\mu(d)

(解释：因为由莫比乌斯函数的定义可知，当c_i>1时，\mu(p^{c_i})=0)

\sum\limits_{d|n'}=\mu(d)=\sum\limits_{i=0}^kC_k^i\cdot(-1)^i

（解释：因为n'的因子全是由质数p_i组成的，所以在n'的k个质因子中选出i个可以组合成n'的所有因子，然后根据选出的质因子个数判断符号是正是负）

(ps:到了这一步有没有发现很像某个定理)

根据二项式定理:

(a+b)^n=\sum\limits_{i=0}^n\dbinom{k}{i}a^{n-i}b^i

得:

\sum\limits_{i=0}^{k}C^i_k\cdot(-1)^i=\sum\limits_{i=0}^{k}\dbinom{k}{i}\times1^{n-i}\times(-1)^i=(1-1)^k=0^k

该式子的值在k=0时即n=1时值为1，否则为0。所以，

\sum\limits_{d|1}^n\mu(d)=[n=1]=\varepsilon(n),\mu*1=\varepsilon

线性筛

问题来了，知道了性质，如何求莫比乌斯函数？

使用线性筛。线性筛基本可以求所有的积性函数，莫比乌斯函数也在其中。

代码：

    mu[1] = 1;
    for(int i=2; i<=N; i++){
        if(!vis[i]) prime[++cnt] = i, mu[i] = -1;//找出素数，素数的莫比乌斯函数值为-1 
        for(int j=1; j<=cnt and i*prime[j] <= N; j++){
            vis[i*prime[j]] = true;//标记以当前素数为最小质因子的合数 
            if(i%prime[j] == 0){
                mu[i*prime[j]] = 0;//如果该合数由两个相同的质因子，莫比乌斯函数值为0 
                break;
            }
            mu[i*prime[j]] = -mu[i]; 
        }
    }

（五）莫比乌斯反演

设f(n),g(n)为两个数论函数，

如果有f(n)=\sum\limits_{d|n}g(d)，那么有g(n)=\sum\limits_{d|n}\mu(d)\cdot f(\dfrac{n}{d})

如果有f(n)=\sum\limits_{n|d}g(d)，那么有g(n) = \sum\limits_{d|n}\mu(\dfrac{d}{n})\cdot f(d)

换一种更加简洁的写法，狄利克雷卷积:

f=g*1\iff f*\mu=g

另外几个常用公式

\varepsilon=\mu*1\iff [x=1]=\sum\limits_{d|n}\mu(d) \varphi*1=\operatorname{id}\iff \varphi=\operatorname{id}*\mu

好了，公式看了这么多，来做几组练习。

练习(练习中设N\leq M)

1.求\sum\limits_{i=1}^N\sum\limits_{j=1}^{M}[\gcd(i,j)=1]

解：原式=\sum\limits_{i=1}^{N}\sum\limits_{j=1}^{M}\varepsilon(\gcd(i,j))

=\sum\limits_{i=1}^{N}\sum\limits_{j=1}^{M}\sum\limits_{d|(i,j)}\mu(d) =\sum\limits_{d=1}^{N}\mu(d)\cdot\sum\limits_{i=1}^{\lfloor\frac{N}{d}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{M}{d}\rfloor}1 =\sum\limits_{d=1}^{N}\mu(d)\lfloor\dfrac{N}{d}\rfloor\lfloor\dfrac{M}{d}\rfloor

2.求\sum\limits_{i=1}^{N}\sum\limits_{j=1}^{M}[\gcd(i,j)=k]

解：原式=\sum\limits_{i=1}^{\lfloor\frac{N}{k}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{M}{k}\rfloor}[\gcd(i,j)=1]

然后用与练习1一样的方式求解即可。

3.求\sum\limits_{i=1}^{N}\sum\limits_{j=1}^{M}\operatorname{lcm}(i,j)

解：原式=\sum\limits_{i=1}^{N}\sum\limits_{j=1}^{M}\dfrac{ij}{\gcd(i,j)}

=\sum\limits_{d=1}^{N}\sum\limits_{i=1}^{N}\sum\limits_{j=1}^{M}[\gcd(i,j)=d]\dfrac{ij}{d} =\sum\limits_{d=1}^{N}d\sum\limits_{i=1}^{\lfloor\frac{N}{d}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{M}{d}\rfloor}ij[\gcd(i,j)=1] =\sum\limits_{d=1}^{N}d\sum\limits_{i=1}^{\lfloor\frac{N}{d}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{M}{d}\rfloor}ij\sum\limits_{x|(i,j)}\mu(x) =\sum\limits_{d=1}^{N}d\sum\limits_{x=1}^{\lfloor\frac{N}{d}\rfloor}\mu(x)x^2\sum\limits_{i=1}^{\lfloor\frac{N}{dx}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{M}{dx}\rfloor}ij =\sum\limits_{d=1}^{N}d\sum\limits_{x=1}^{\lfloor\frac{N}{d}\rfloor}\mu(x)x^2\dfrac{\lfloor\frac{N}{dx}\rfloor(\lfloor\frac{N}{dx}\rfloor+1)\lfloor\frac{M}{dx}\rfloor(\lfloor\frac{M}{dx}\rfloor+1)}{4}

真不容易~

留坑待补。

参考资料OIWiki(https://oi-wiki.org/math/mobius/)