莫比乌斯反演

未分类

---

如果你做题见到好多个$\sum$,例如：

$$\sum\limits_{i=1}^n\sum\limits_{j=1}^n gcd(i, j)$$
这种东西，那么你就可能会需要用到莫比乌斯反演。
你需要先学两个前置知识：[数论分块]、[狄利克雷卷积]

数论分块

数论是研究整数的。
既然是整数而不是实数那么他就有一些奇怪的性质。
其中一个性质便是除法向下取整。
比如说：：

$$12÷5=2$$
$$12÷6=2$$
再比如：
$$15÷4=3$$
$$15÷5=3$$
不难发现一个数去和一些数做除法，有很多结果相同的，
尤其是后期，重复的越来越多：
$$15÷8=1$$
$$15÷9=1$$
$$……$$
$$15÷14=1$$
$$15÷15=1$$
太多一样的了！！！
而且对于一个被除数来说，答案相同的除数都是连续的，来个直观一点的：

可见被分成了一块一块的，那么我们把这些块同时处理，这就叫做数论分块。
怎么同时处理呢？
首先你要知道什么叫下取整。
$$\lfloor\frac{5}{3}\rfloor=1$$
$$\lfloor\frac{5}{2}\rfloor=2$$
$$\lfloor\frac{被除数}{除数}\rfloor=商……余数(不看余数只看商)$$
那么开始引入性质：

引理1：

$$\lfloor\frac{a}{bc}\rfloor=\lfloor\frac{\lfloor\frac{a}{b}\rfloor}{c}\rfloor$$
证：
$$∵\frac{a}{b}=\lfloor\frac{a}{b}\rfloor+r(0\le r<1)$$
$$∴\lfloor\frac{a}{bc}\rfloor=\lfloor\frac{a}{b}·\frac{1}{c}\rfloor=\lfloor\frac{1}{c}(\lfloor\frac{a}{b}\rfloor+r)\rfloor=\lfloor\frac{\lfloor\frac{a}{b}\rfloor}{c}+\frac{r}{c}\rfloor$$
其中$\frac{r}{c}<1$，我们可以无视他。
$$∴\lfloor\frac{\lfloor\frac{a}{b}\rfloor}{c}+\frac{r}{c}\rfloor=\lfloor\frac{\lfloor\frac{a}{b}\rfloor}{c}\rfloor$$
$$∴\lfloor\frac{a}{bc}\rfloor=\lfloor\frac{\lfloor\frac{a}{b}\rfloor}{c}\rfloor$$
这时候我知道你会问，为什么$\lfloor\frac{\lfloor\frac{a}{b}\rfloor}{c}+\frac{r}{c}\rfloor$这里面 $\frac{r}{c}$ 可以被无视。
$\frac{\lfloor\frac{a}{b}\rfloor}{c}$ 得到的是实数，而 $\frac{r}{c}$ 也是个实数。
前者的小数部分和后者加起来万一一不小心大于 $1$ 了,那么省不省略 $\frac{r}{c}$ 结果不就不一样了吗？
但是你想！！！$\lfloor\frac{a}{b}\rfloor$ 是个整数，$c$ 也是整数，两个整数相除得到的小数部分最大应该是 $\frac{c-1}{c}$
而 $0\le r<1$,所以 $\frac{r}{c}<\frac{1}{c}$
$$∴\frac{c-1}{c}+\frac{r}{c}<\frac{c}{c}$$
$$∴\frac{c-1}{c}+\frac{r}{c}<1$$
所以 $\frac{r}{c}$ 是可以忽略的。

引理2 (关键！！)：

当 $i$ 已知
要满足

$$\lfloor\frac{n}{j}\rfloor=\lfloor\frac{n}{i}\rfloor~~(1\le i\le j\le n)$$
的最大的 $j$ 即 $i$ 所在块的右端点为
$$\lfloor\frac{n}{\lfloor\frac{n}{i}\rfloor}\rfloor$$
证：
$$∵\lfloor\frac{n}{i}\rfloor\le\frac{n}{i}$$
$$∴\lfloor\frac{n}{\frac{n}{i}}\rfloor\le \lfloor\frac{n}{\lfloor\frac{n}{i}\rfloor}\rfloor$$
其中：
$$∴\lfloor\frac{n}{\frac{n}{i}}\rfloor=\lfloor i\rfloor=i$$
$$∴i<=\lfloor\frac{n}{\lfloor\frac{n}{i}\rfloor}\rfloor$$
$$∴j_{max}<=\lfloor\frac{n}{\lfloor\frac{n}{i}\rfloor}\rfloor$$
##
那么我们现在就可以用数论分块去加速一些运算了，来个例题：
$$求\sum\limits_{i=1}^{n}\lfloor\frac{n}{i}\rfloor$$
多组数据，保证数据中 $n$ 的总和小于 $10^{14}$
显然得用 $O(\sqrt{n})$ 的做法了，那么我们现在可以直接数论分块，毕竟是板子。
如果你上边看懂了，那就直接看代码：

ll t,n,ans;
int main(){
  t=read();
  while(t--) {
    n=read();
    ans=0;
    ll l=1, r;\\从1开始
    while(l<=n) {
      r=n/(n/l);//这是l的块的右端点
      ans+=(r-l+1)*(n/l);//直接区间求和
      l=r+1;//下一个块
    }
    printf("%lld\n", ans);
  }
}

很简单吧， 很好理解吧。

好那么现在证明一下复杂度：

我们是一个个块枚举的，所以复杂度就是有几个块算几次。
相同的值算一个块，那么就看 $\lfloor\frac{n}{i}\rfloor$ 有几种取值就行。
①当$i\le\sqrt{n}$
就算 $\lfloor\frac{n}{i}\rfloor$ 互不相同，
撑死 $\sqrt{n}$ 种取值。
②当$\sqrt{n}\le i$
$∵\lfloor\frac{n}{\sqrt{n}}\rfloor\le\sqrt{n}$
所以也是撑死只有 $\sqrt{n}$ 个取值
总共撑死只有 $2\sqrt{n}$ 个块。
所以复杂度 $O(\sqrt{n})$

还有一个，叫做多维数论分块。

比如

$$\sum\limits_{i=1}\lfloor\frac{n}{i}\rfloor\lfloor\frac{m}{i}\rfloor$$
很简单，对 $n$，$m$ 分别算右端点取 $min$ 就行

r=n/(n/l);
->
r=min(n/(n/l), m/(m/l));

二维以上同理。
就这么点东西，就这么简单~

狄利克雷卷积

一个很神奇的东西。
两个数论函数 $f$，$g$，我们定义，不要问为啥，就是定义，其狄利克雷卷积为:

$$(f*g)(n)=\sum\limits_{d|n}f(d)×g(\frac{n}{d})$$
然后，你就很神奇的能把两个函数建立起这么一种神奇的关系来。
为什么说神奇呢？

1.交换律

$$(f*g)(n)=\sum\limits_{d|n}f(d)×g(\frac{n}{d})$$
显然我枚举了 $n$ 的因子
那我枚举 $d$ 是 $n$ 的所有因子。
显然 $\frac{n}{d}$ 也是 $n$ 的所有因子。
$n$ 和 $\frac{n}{d}$ 也一直是一一对应的
所以就等价了。
$$(f*g)(n)=\sum\limits_{d|n}f(d)×g(\frac{n}{d})$$
$$~~~~~~~~~~~~~~~~~=\sum\limits_{d|n}f(\frac{n}{d})×g(d)$$
$$~~~~~~~=(g*f)(n)$$
简写：
$$f*g=g*f$$

2.结合律

$(f*g)*h=f*(g*h)$
直接上：

$$(f*g)*h=\sum\limits_{d|n}h(\frac{n}{d})×(\sum\limits_{x|d}f(x)×g(\frac{d}{x}))$$
显然的：
$$x×\frac{d}{x}×\frac{n}{d}=n$$
所以：
$$(f*g)*h=\sum\limits_{abc=n}f(a)×g(b)×h(c)$$
看到这一点了就好办了，这个式子的对称性很强。
$$f*(g*h)=\sum\limits_{abc=n}g(a)×h(b)×f(c)$$
一个是先算 $f*g$，一个是先算 $g*h$ ，不过在这个形式的式子中，谁前谁后重要吗？都一样！！！
得证！！

3.分配律

$(f+g)*h=f*h+g*h$
设

$$F(n)=f(n)+g(n)$$
则有
$$F*h=\sum\limits_{d|n}F(d)×h(\frac{n}{d})$$
$$~~~~~~~~~~~~~~~~~~~~~~~=\sum\limits_{d|n}(f(d)+g(d))×h(\frac{n}{d})$$
$$~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~=\sum\limits_{d|n}f(d)×h(\frac{n}{d})+\sum\limits_{d|n}g(d)×h(\frac{n}{d})$$
$$~~~=f*h+g*h$$

前置知识储备完毕，现在我们正式开始讲——莫比乌斯反演

莫比乌斯反演

接下来正式开始学习。
首先你要知道几个定义：

• 元函数：$e(n)=[n==1]$
• 单位函数：$id(n)=n$
• 恒等函数：$I(n)=1$
• 莫比乌斯函数： $μ(n)=\begin{cases}1&n=1\\(-1)^k&n=\prod\limits_{i=1}^kp_i(n能表示成k个质数的1次幂的乘积)\\0&other\end{cases}$
  接下来，我们先看一下莫比乌斯函数的一条重要性质：
  $$\sum\limits_{d|n}μ(d)=[n==1]$$
  也就是说：
  $$e(d)=\sum\limits_{d|n}μ(d)$$
  证：
  $$当n=1时，μ(1)=1$$
  其他情况只考虑能被表示成若干个质数的 $1$次幂的乘积的数
  这时候 $n$ 这个数有用的只有他的所有质因子的 $1$ 次幂。
  那么只需要考虑:
  $$n'=\prod\limits_{i=1}^kp_i$$
  即： $$\sum\limits_{d|n}μ(d)=\sum\limits_{d|n'}μ(d)$$
  那我们直接枚举 $d$ 也就是枚举 $n'$ 的因子。
  而对于 $n'$ 这么个特殊的数，它的质因子是什么呢。
  $$C_k^i$$
  对的，从 $k$ 个质因子里任意选 $i$ 个质因子，组成的数就是不重复的所有 $n$ 的因子。
  那
  $$\sum\limits_{d|n'}μ(d)=\sum\limits_{i=0}^kC_k^i×(-1)^i$$
  如果你对二项式定理很敏感的话，这式子也就很简单了。
  $$(x+y)^k=\sum\limits_{i=0}^kC_k^i×x^i×y^{k-i}$$
  这个时候，我么对 $y$ 取 $1$, $x$ 取 $-1$
  就有了：
  $$\sum\limits_{i=0}^kC_k^i×(-1)^i×1$$
  和原式是一样的！！！
  那么回过头看 $(x+y)^k$,当 $x=-1,y=1$ 时：
  $$(x+y)^k=(-1+1)^k=0$$
  综上：
  $$\sum\limits_{d|n}μ(d)=e(d)=[n==1]$$

反演：

我们设：

$$f(n)=\sum\limits_{d|n}g(d)$$
那我们能不能用 $f$ 表示 $g$ 呢？

我们可以直接利用狄利克雷卷积来表示：

$$∵\sum\limits_{d|n}g(d)=\sum\limits_{d|n}g(d)×I(\frac{n}{d})=g*I$$
$$∴f=g*I$$
$$∴f*μ=g*I*μ$$
$$∵ I*μ=\sum\limits_{d|n}μ(d)I(\frac{n}{d})=\sum\limits_{d|n}μ(d)=e$$
$$∴f*μ=g*e$$
$$∵g*e=\sum\limits_{d|n}g(d)×e(\frac{n}{d})=g(只有e(1)有贡献)$$
$$∴f*μ=g$$
$$∴g(n)=\sum\limits_{d|n}f(d)×μ(\frac{n}{d})$$
此乃反演！！！
会了一个知识点
不做习题怎么行？
回到开头：
$$\sum\limits_{i=1}^n\sum\limits_{j=1}^n gcd(i, j)$$
这直接 $O(n^2logn)$
$n\le10^6$……
好，开始化简！：
$$\sum\limits_{i=1}^n\sum\limits_{j=1}^n gcd(i, j)$$
$$=\sum\limits_{k=1}^nk\sum\limits_{i=1}^n\sum\limits_{j=1}^n [gcd(i, j)==k]$$
$$=\sum\limits_{k=1}^nk\sum\limits_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{n} {k}\rfloor} [gcd(i, j)==1]$$
$$=\sum\limits_{k=1}^nk\sum\limits_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{n} {k}\rfloor} e(gcd(i, j))$$
$$=\sum\limits_{k=1}^nk\sum\limits_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{n} {k}\rfloor}\sum\limits_{d|gcd(i,j)} μ(d)$$
现在我们转化一下求和顺序，现枚举 $d$
$$=\sum\limits_1^kk\sum\limits_{d=1} μ(d)\sum\limits_{i=1}^{\lfloor\frac{n}{k}\rfloor}[d|i]\sum\limits_{j=1}^{\lfloor\frac{n} {k}\rfloor}[d|j]$$
其中，$\sum\limits_{i=1}^{\lfloor\frac{n}{k}\rfloor}[d|i]$ 就是求 $\lfloor\frac{n}{k}\rfloor$ 里 $d$ 的倍数啊。
继续：
$$=\sum\limits_1^nk\sum\limits_{d=1} μ(d)\lfloor\frac{n}{kd}\rfloor\lfloor\frac{n}{kd}\rfloor$$
$$=\sum\limits_1^nk\sum\limits_{d=1} μ(d)\lfloor\frac{n}{kd}\rfloor^2$$
其中 $\lfloor\frac{n}{kd}\rfloor$ 可以数论分块
$\sum\limits_{d=1} μ(d)$ 可以用前缀和快速求。
问题来了每一个 $μ(d)$ 怎么求？
线性求！！
因为它是积性的！！
直接在欧拉筛里求！
上代码：

void Euil() {
  mu[1]=1;
  for(int i=2; i<=1000000; ++i) {
    if(!pd[i]) {
        zhi[++top]=i;
        mu[i]=-1;//一个质数(-1)^1 
    }
    for(int j=1; j<=top&&zhi[j]*i<=1000000; ++j) {
        pd[zhi[j]*i]=1;
        if(i%zhi[j]==0) break;
        else mu[zhi[j]*i]=-mu[i];//一个新的质数。 
    }
    }
    for(int i=1; i<=1000000; ++i) {
    mu[i]+=mu[i-1];
    }
} 
int main(){
    n=read();
    for(int k=1; k<=n; ++i) {
    int l=1, r;
    int nn=n/k;
    while(l<=nn) {
        r=nn/(nn/l);
        int p=nn/l;
        ans+=k*p*p*(mu[r]-mu[l-1]);
        l=r+1;
    }   
    } printf("%d", ans);
}

---

特别鸣谢， @Konnyaku41377 提供的详细理论及知识点讲解

感谢大家的阅读，多多点赞哟~