本文主要介绍莫比乌斯反演(mobius-inversion),其本质就是在质因数上进行容斥,常用于解决一些关于 gcd\gcd 的问题。

莫比乌斯函数

nn 的分解式为 n=p1a1p2a2pkakn=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}

μ(i)={1i=1(1)kak=10ak>1 \mu(i)= \begin{cases} 1&i=1 \\ (-1)^k&\forall a_k=1 \\ 0&\exists a_k\gt1 \end{cases}

莫比乌斯函数的重要性质

dnμ(d)={1(n=1)0(n1) \sum_{d\mid n}\mu(d)= \begin{cases} 1 &(n=1) \\ 0 &(n\neq1) \end{cases}

其本质为在质因数上的进行容斥,利用 n=1n=1 的特例可以计算如 [gcd(a,b)=1][\gcd(a,b) = 1] 的问题。

莫比乌斯函数求欧拉函数

φ(n)=i=1n[gcd(i,n)=1]=i=1nki,knμ(k)=knμ(k)nk\varphi(n)=\sum\limits_{i=1}^n[\gcd(i,n)=1]=\sum\limits_{i=1}^n\sum\limits_{k\mid i,k\mid n}\mu(k)=\sum\limits_{k\mid n}\mu(k)\lfloor\frac nk\rfloor

莫比乌斯反演

  • f(n)=dng(d)g(n)=dnμ(d)f(nd)f(n)=\sum\limits_{d\mid n}g(d) \rightarrow g(n)=\sum\limits_{d\mid n}\mu(d)f(\frac nd)
  • f(n)=ndNg(d)g(n)=ndNf(d)μ(dn)f(n)=\sum\limits_{n\mid d}^Ng(d)\rightarrow g(n)=\sum\limits_{n\mid d}^Nf(d)\mu(\frac dn)

莫比乌斯反演的应用

i=1nj=1m[gcd(i,j)=1]\sum\limits_{i=1}^n\sum\limits_{j=1}^m[\gcd(i,j)=1]

f(x)=i=1nj=1m[gcd(i,j)=x]f(x) = \sum\limits_{i=1}^n\sum\limits_{j=1}^m[\gcd(i,j)=x] ,则
g(x)=xdf(d)=i=1nj=1m[xgcd(i,j)]=i=1nxj=1mx[1gcd(i,j)]=nxmxg(x)=\sum\limits_{x|d} f(d) = \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m} [x \mid \gcd(i,j)] = \sum\limits_{i=1}^{\lfloor \frac nx \rfloor}\sum\limits_{j=1}^{\lfloor \frac mx \rfloor} [1 \mid \gcd(i,j)] = \lfloor \frac nx \rfloor \lfloor \frac mx \rfloor

莫比乌斯反演,有

f(1)=i=1nμ(i)g(i)=i=1nμ(i)nimif(1) = \sum\limits_{i=1}^{n} \mu(i) g(i) = \sum\limits_{i=1}^{n} \mu(i) \lfloor \frac ni \rfloor \lfloor \frac mi \rfloor

可以在 O(n)\mathcal{O (n)} 的时间内完成计算。


相关题目

[BZOJ2301][HAOI2011]Problem b

题意:有 TT 次询问,每次给出 x[a,b],y[c,d]x \in [a,b], y \in [c,d] ,求满足 gcd(x,y)=k\gcd(x,y) = k 的二元组 (x,y)(x,y) 的个数。

数据范围:1T50000,1ab50000,1cd50000,1k500001 \le T \le 50000, 1 \le a \le b \le 50000, 1 \le c \le d \le 50000, 1 \le k \le 50000


[BZOJ2154]Crash的数字表格

题意:计算 i=1nj=1nlcm(i,j)\sum\limits_{i=1}^n\sum\limits_{j=1}^n \text{lcm} (i,j) 。 ( n,m107n,m \le 10^7 )

[BZOJ2226][Spoj 5971]LCMSum

题意: T300000T \le 300000 组数据, 计算 i=1nlcm(i,n)\sum\limits_{i=1}^n \text{lcm} (i,n) 。 ( n1000000n \le 1000000 )

i=1nlcm(i,n)=i=1ningcd(i,n)=dni=1nind[gcd(i,n)=d]=ndni=1ndi[gcd(i,nd)=1]=ndni=1di[gcd(i,d)=1] \begin{aligned} \sum_{i=1}^n \text{lcm} (i,n)&=\sum_{i=1}^n\frac{i\cdot n}{\gcd(i,n)} \\ &=\sum_{d\mid n}\sum_{i=1}^n\frac{i\cdot n}{d}[\gcd(i,n)=d] \\ &=n\sum_{d\mid n}\sum_{i=1}^{\frac nd}i[\gcd(i,\frac nd)=1] \\ &=n\sum_{d\mid n}\sum_{i=1}^{d}i[\gcd(i,d)=1] \end{aligned}

f(n)=i=1ni[gcd(i,n)=1]f(n)=\sum\limits_{i=1}^{n}i[\gcd(i,n)=1] ,其具体意义为 n\le n 且与 nn 互质的数的和。
n2n \ge 2 时,若存在 ppnn 互质 ( pnp \le n ),则 gcd(np,1)=gcd(n,p)=1\gcd(n-p,1) = \gcd(n,p) = 1 。故 f(n)=nϕ(n)2f(n) = n \cdot \frac{\phi(n)}{2}
所以可以 O(n ln n)\mathcal{O} (n~ln~n) 预处理答案, 询问 O(1)\mathcal{O} (1)

[BZOJ2671]jzptab

题意: T10000T \le 10000 组数据, 计算 i=1nj=1nlcm(i,j)\sum\limits_{i=1}^n\sum\limits_{j=1}^n \text{lcm} (i,j) 。 ( n,m107n,m \le 10^{7} )


[BZOJ2671]Calc

题意:求出满足 1a<bN1 \le a < b \le Na+baba+b \mid ab 的数对 (a,b)(a,b) 的个数。

gcd(a,b)=d\gcd(a,b) = da+baba+babda+bda+b\mid ab\Rightarrow a'+b'\mid a'b'd\Rightarrow a'+b'\mid d 。题意转化为满足 (a,b)=1(a,b) = 1a+bda+b \mid d(a,b)(a,b) 数量。
再考虑后一个限制,有 dnb,bnd\le\lfloor\frac nb\rfloor , b \le \sqrt{n} ,故 a+bda+b \mid d 产生的答案为 nba+b=n(a+b)b\left\lfloor\frac{\lfloor\frac nb\rfloor}{a+b}\right\rfloor=\left\lfloor\frac{n}{(a+b)b}\right\rfloor

ans=b=1ma=1b1[gcd(a,b)=1]n(a+b)b=b=1ma=1b1da,dbμ(d)n(a+b)b=dμ(d)dbmdab1n(a+b)b=dμ(d)b=1mda=1b1nd2b(a+b) \begin{aligned} ans&=\sum_{b=1}^m\sum_{a=1}^{b-1}[\gcd(a,b)=1]\left\lfloor \frac{n}{(a+b)b}\right\rfloor \\ &=\sum_{b=1}^m\sum_{a=1}^{b-1}\sum_{d\mid a,d\mid b}\mu(d)\left\lfloor \frac{n}{(a+b)b}\right\rfloor \\ &=\sum_d\mu(d)\sum_{d\mid b}^m\sum_{d\mid a}^{b-1}\left\lfloor \frac{n}{(a+b)b}\right\rfloor \\ &=\sum_d\mu(d)\sum_{b=1}^{\lfloor \frac md\rfloor}\sum_{a=1}^{b-1}\left\lfloor \frac{n}{d^2b(a+b)}\right\rfloor \end{aligned}

可以对 a+ba+b 进行数论分块,时间复杂度 O(n34n12)\mathcal{O(n^{\frac 34}-n^{\frac 12})}


参考资料