莫比乌斯反演
前言
- 莫比乌斯反演是数论中的一个重要的内容，对于一些函数(f(n))，如果很难直接求出他的值，而容易求出他的倍数和或约数和(g(n))，那么可以通过莫比乌斯反演简化运算，求得(f(n))的值。
- 博文中有部分内容会先不给出证明，因为证明需要狄利克雷卷积的前置知识，过分关注狄利克雷卷积我个人认为不太利于莫比乌斯反演的学习。
- 但他们又是紧密联系的一个内容，所以在文末最后一部分会有证明。
前置知识
整除分块
- 直接来看这样一道题吧：洛谷2261：余数求和
莫比乌斯函数
- 看一下这篇博客吧~！莫比乌斯函数。
性质
- 性质1：莫比乌斯函数是一个积性函数。
- 性质2：对于任意正整数(n)，有(sum_{d|n}frac{mu(d)}{d}=frac{phi(n)}{n})。其中(phi(n))是(n)的欧拉函数。
- 性质3：对于任意正整数(n)，(sum_{d|n}mu(d)= (n=1))。（常用）
- 也就是说这个式子只有当(n=1)时返回值为(1)，否则返回值为(0)。
- 证明：
- 1：当(n=1)显然。
- 2：当(n eq 1)时，根据算术基本定理有(n=p_1^{c_1}p_2^{c_2},...,p_k^{c_k})。
- 对于(c_i >= 2)的情况，莫比乌斯函数都等于0。
- 所以只用考虑(c_i=1)的情况。
- 质因数为(r)的个的因子有(C_k^r)个。
- 那么显然有(sum_{d|n}=C_k^0-C_k^1+C_k^2+...+(-1)^kC_k^k=sum_{i=0}^k(-1)^iC_k^i=0)。
莫比乌斯反演
莫比乌斯反演定理
- (F(n))和(f(n))是定义在非负整数集合上的两个函数，并满足条件：
- (F(n)=sum_{d|n}f(d)).
- 那么有:
- (f(n)=sum_{d|n}mu(d)F(lfloorfrac{n}{d} floor)).
- 这个定理就是莫比乌斯反演定理。
- 还有另一种表现形式：
- (F(n)=sum_{n|d}f(d)).
- (f(n)=sum_{n|d}mu(lfloorfrac{d}{n} floor)F(d))。
例题
难度递增
上述部分性质的证明：
积性函数：
定义：
- (f(n))是积性函数，则有：(f(1)=1)，且若(a,b)互质，则(f(ab)=f(a)f(b))。
- 如果对于(a,b)不一定互质，也满足上述性质，则这个函数被称为完全积性函数。
常见的积性函数
- (mu(n))：莫比乌斯函数。
- (phi(n))：欧拉函数，表示从(1)到(n)中与(n)互质的数的个数。
- (d(n))：约数个数，就是(n)的约数的个数。
- (sigma(n))：约数和函数。
完全积性函数
- (epsilon(n))：元函数。(epsilon(n)=[n=1])。
- (id(n))：单位函数。(id(n)=n)。
- (I(n))：恒等函数，(I(n)=1)，不管(n)取多少，这个函数都恒为(1)。
积性函数的性质：
- 设(f(x),g(x))为积性函数，则：
- (h(x)=f(x^p)).
- (h(x)=f^p(x)).
- (h(x)=f(x)g(x)).（重要，也就是积性函数*积性函数=积性函数）
- (h(x)=sum_{d|x}f(d)g(frac{x}{d})).
- 中的(h(x))也为积性函数。
狄利克雷卷积（*）
定义
-
不需要把他当成很难的东西，就想成他是一个符号定义了一个运算就行。
-
定义：两个数论函数(f)和(g)的卷积为((f*g)(n)=sum_{d|n}f(d)g(frac{n}{d}))。
- 前面的符号表示(f)卷(g)，后面的括号表示范围。
性质
- 1：交换律：(f*g=g*f).
- 2：结合律：((f*g)*h=f*(g*h)).
- 3：分配律：((f+g)*h=f*h+g*h).
- 前面那个元函数(epsilon)：
- 所谓元函数，就是在狄利克雷卷积卷积中充当单位元的作用。即(f*epsilon=f)。
莫比乌斯函数(mu)
-
有性质：(sum_{d|n}=mu(d)=[n=1])。
-
首先证明莫比乌斯反演：
-
已知(F(n)=sum_{d|n}f(d))。
-
用狄利克雷卷积来表示这个式子：
- (F=f*I).
- 其中(I(n))是恒等函数。
-
利用地理科类卷积将(F)卷上(u)，则有：
- (F*u=f*I*u)。
-
根据狄利克雷卷积的结合律有：
- (f*(I*u)=f*epsilon=f).
- 根据性质三推出来的。
- ((I*u)(n)=sum_{d|n}mu(d)I(frac{n}{d})=sum_{d|n}mu(d)=[n=1]=epsilon(n)).
-
即：
- (F*u=f).
- (f(n)=sum_{d|n}mu(d)F(frac{n}{d})).
欧拉函数(phi)
- 欧拉函数的著名性质：(sum_{d|n}phi(d)=n)。
- 将其表现为狄利克雷卷积形式：
- (phi*I=sum_{d|n}phi(d)I(frac{n}{d})=sum_{d|n}phi(d)=n=id(n)).
- (phi*I=id).
- 其中(id(n))是单位函数，(id(n)=n)。
- 两边同卷上一个(u)：
- (phi*I*mu=id*mu).
- (phi*(I*mu)=phi*epsilon=phi=id*mu=sum_{d|n}mu(d)id(frac{n}{d})=sum_{d|n}mu(d)frac{n}{d}).
- 两个公式同时除以(n)，有：
- (sum_{d|n}frac{mu(d)}{d}=frac{phi(n)}{n})。