莫比乌斯反演

莫比乌斯反演:

F(x)f(x)为定义在非负整数集合上的两个函数,并且满足
$$ F(n) = \sum_{d\mid n}f(d) $$
则有:
$$ f(n) = \sum_{d\mid n}\mu (d)F(\frac{n}{d})$$
其中\mu为莫比乌斯函数,定义为:
\mu(1)=1
\mu(n)=(-1)^k,若n为k个不同素数之积;
\mu(n)=0,其他情况

证明:

几个定义:

  1. 狄利克雷卷积:
    两个数论函数f,g的狄利克雷卷积为:
    (f\times g)(n)=\sum_{d\mid n}f(d)\cdot g(\frac nd)
    狄利克雷卷积满足:

    • 交换律:
      f \times g=g\times f
    • 结合律:
      (f\times g)\times h = f\times (g\times h)
      证:
      左边:
      $$ ((f\times g)\times h)(n) = \sum_{lk=n}(f\times g)(l)h(k) = \sum_{lk=n}(\sum_{ij=l}f(i)g(j))h(k) = \sum_{ijk=n}f(i)g(j)h(k)$$
      右边同理。
  2. 单位元函数\varepsilon \times f = f
    \varepsilon (n) = [n==1]

  3. 1函数:
    1(n)=1

  4. 莫比乌斯函数\mu
    1在卷积意义下的逆元称为莫比乌斯函数,即:
    1 \times \mu = \epsilon
    莫比乌斯函数的定义见开头,证略。

接下来证明莫比乌斯反演:
有了以上定义,莫比乌斯反演可以写成:
$$F=f\times 1\Rightarrow f=F\times \mu$$
左式两边同时乘以\mu即得证。

几道例题

bzoj1101

题意:对于给定的整数a,b和d,有多少正整数对(x,y),满足x\leq a, y\leq b并且gcd(x,y)=d
解法:设a \leq b
$$
ans = \sum_{i=1}^{a}\sum_{j=1}^{b}[gcd(i, j)==d] $$
$$= \sum_{i=1}^{\lfloor a/d\rfloor}\sum_{j=1}^{\lfloor b/d\rfloor}[gcd(i,j)==1] $$
$$= \sum_{i=1}^{\lfloor a/d\rfloor}\sum_{j=1}^{\lfloor b/d\rfloor}\sum_{k\mid gcd(i, j)}\mu(k) $$
$$= \sum_{k=1}^{\lfloor a/d\rfloor}\mu(k)\lfloor\frac a{kd}\rfloor\lfloor\frac b{kd}\rfloor $$
由于\lfloor a/k\rfloor只有最多2\sqrt{a}种取值,所以可以分块一下。

bzoj2820

题意:给定n, m,求1\leq x\leq n, 1\leq y\leq mgcd(x, y)为质数的(x, y)有多少对
解法:设n\leq m
对于每一个质数p,有
$$
ansp =\sum_{d=1}^{\lfloor n/p\rfloor}\mu(d)\lfloor\frac n{pd}\rfloor\lfloor\frac m{pd}\rfloor $$
t=pd,则
$$ansp = \sum_{t=1}^{n}\sum_{isprime(p)\bigwedge p\mid t}\mu(\frac tp)\lfloor\frac nt\rfloor\lfloor\frac mt\rfloor$$
其中$$F(t)=\sum_{isprime(p)\bigwedge p\mid t}\mu(\frac tp)$$可以线性预处理。然后就跟上一题一样了。

bzoj2301

题意:求有多少个数对(x,y),满足a\leq x\leq bc\leq y\leq d,且gcd(x,y) = k
解法:跟第一题一样区间加加减减就行了。

vijos1889

题意:如果一个数的每个质因数的指数都为1,则小岛可以将它分解。问第k个小岛不能分解的数是多少。
解法:二分答案n,看比n小的不能分解的数有多少。若一个数不能被分解,它一定是某个完全平方数的倍数,也就是说要求小于等于n的是完全平方数的倍数的数的个数,这个用莫比乌斯函数容斥一下就好了。
$$ansn = \sum_{i=1}^{n}\mu(i)\lfloor\frac n{i^2}\rfloor$

bzoj3529

题意:有一张n×m的数表,其第i行第j列的数值为能同时整除i和j的所有自然数之和。给定a,计算数表中不大于a的数之和。

n\leq m
我们先把a的限制去掉。
设$$ f(i)=\sum_{d\mid i}d,g(i)=\sum_{x=1}^{n}\sum_{y=1}^m[gcd(x, y)==i]$$

$$g(i)=\sum_{i\mid t}\mu(\frac ti)\lfloor\frac nt\rfloor\lfloor\frac mt\rfloor$$
$$ans=\sum_{i=1}^{n}f(i)g(i)=\sum_{i=1}^{n}f(i)\sum_{i\mid t}\mu(\frac ti)\lfloor\frac nt\rfloor\lfloor\frac mt\rfloor=\sum_{t=1}^{n}\lfloor\frac nt\rfloor\lfloor\frac mt\rfloor\sum_{i\mid t}f(i)\mu(\frac ti)$$
F(t)=\sum_{i\mid t}f(i)\mu(\frac ti),我们只要求出F的前缀和就可以老样子分块了。
现在多了限制a,然后我们发现对于限制a只有f(x) \leq a的x对答案有贡献,于是就可以按照a从小到大离线,每次把小于等于当前a的f(x)对应的F(x)加入树状数组维护前缀和。

bzoj2154

题意:求\sum_{i=1}^{n}\sum_{j=1}^{m}lcm(i, j)

n\leq m
$$ans= \sum_{i=1}^{n}\sum_{j=1}^{m}\frac{i\cdot j}{gcd(i, j)}$$
$$=\sum_{d=1}^{n}\sum_{gcd(i, j)==d}\frac {i*j}d$$
$$=\sum_{d=1}^{n}\sum_{i=1}^{\frac nd}\sum_{j=1}^{\frac md}d\cdot i\cdot j\sum_{k\mid gcd(i,j)}\mu(k)$$
$$=\sum_{d=1}^{n}d\cdot\sum_{k=1}^{\frac nd}\mu(k)\cdot k^2\cdot F(\lfloor\frac n{dk}\rfloor,\lfloor\frac m{dk}\rfloor)$$
其中F(x, y)=\sum_{i=1}^x\sum_{j=1}^y i\cdot j
F可以O(1)算,于是就分块分块。。

发表评论