【学习笔记】$\mu$ 函数的性质

众所周知 $\mu$ 函数具有如下性质:

大部分有关于 $\gcd$ 、带有艾佛森括号的反演题目都可以用这个性质解决。

证明方式有很多,此处采用狄利克雷卷积的方式来比较简洁地证明。

根据 $\mu$ 的定义,$\mu*\boldsymbol{1}=\boldsymbol{I}$,那么有

当然,其实还有更优美的证法。思考 $\mu$ 的本质,当 $n$ 含有平方因子的时候,$\mu(n)=0$;否则 $\mu(n)=(-1)^k$,其中 $k$ 是 $n$ 的本质不同质因子个数。

接下来考虑一步转化。设 $n=\sum p_i^{e_i},n’=\sum{p_i}$ 。那么有

所以到最后 $[k=0]$ 就意味着 $[n=1]$ 。$\mathcal{Q.E.D.}$

默认 $(a,b)$ 代表 $a$ 与 $b$ 的最大公约数,$|$ 表示整除。

$1$

$1\leq n\leq m\leq 10^6,q\leq 50000$

其实就是代换:

然后就可以 $O(n)+O(q\sqrt n)$ 来做了。

但其实本质上,$n$ 可以出到 $10^9$ ?但是总感觉杜教筛套上一层数论分块复杂度就不是很对了。此处可能还需要思考思考。

$2$

[POI2007]ZAP-Queries/LG4450双亲数

$1\leq n\leq m\leq 10^6,q\leq 50000$

其实本质上是一样的。

$3$

$\forall p\in\mathbb{P}$,求

$1\leq n\leq m\leq 10^7,q\leq 10000$

发现到最后变成了这样:

考虑继续换元,令 $q=p_kd$,枚举 $q$:

然后发现前半部分可以数论分块,后半部分可以直接在筛素数的时候 $dp$ 出来即可。

1
2
3
4
for (i = 1 ; i <= cnt ; ++ i)
for (j = 1 ; Pr[i] * j <= MAXN - 15 ; ++ j)
f[j * Pr[i]] += Mu[j] ;
for (i = 1 ; i <= MAXN - 15 ; ++ i) S[i] = S[i - 1] + f[i] ;

$4$

题目来自神仙李思杰的 $blog$:

$1\leq n,m\leq 10^6$

发现可以这么做:

发现后面是个简单的二阶求和形式,故至此已经可以分快了。

$5$

[SDOI2015]约数个数和

$1\leq n,m\leq 10^6,1\leq q\leq 10^5$

首先考虑一步几乎想不出来的转化:

可以类似线性筛那样感性理解。

然后就可以直接做了:

发现后面这东西可以很简单地

预处理,所以复杂度 $O(q\cdot\sqrt n)$