莫比乌斯反演

· · 个人记录

前置：积性函数与狄利克雷卷积 和 整除分块

两个基础积性函数：\varepsilon(n)=[n=1]，1(n)=1。

性质：\varepsilon*f=f，f 是任意函数。

结论：f(n) 是积性函数 \iff g(n)=\displaystyle\sum_{d|n}f(d) 是积性。

证明：

$\Leftarrow$ 方向：归纳法。 1. $g(1)=f(1)$。由于 $g$ 积性，所以 $g(1)=g(1)g(1)$，所以 $g(1)=f(1)=1$。 2. 对于 $n>1$，设 $n=ab,\;(a,b)=1$。归纳法知 $f(1)\sim f(n-1)$ 是积性函数。 $$g(n)=g(ab)=\displaystyle\sum_{d|ab}f(d)$$ $$=\displaystyle\sum_{d_1|a}\sum_{d_2|b}f(d_1d_2)$$ 注意一下，当 $d_1=a,d_2=b$ 时，$d_1d_2=n$，这里我们还不知道 $f(n)$ 是积性的。所以我们要把这种情况拆出来单独考虑。 $$=\displaystyle(\sum_{d_1|a}\sum_{d_2|b}f(d_1)\cdot f(d_2))-f(a)f(b)+f(ab)$$ 另外，有条件 $g$ 是积性函数，所以 $$g(n)=g(a)g(b)=\displaystyle\sum_{d_1|a}f(d_1)\sum_{d_2|b}f(d_2)=\sum_{d_1|a}\sum_{d_2|b}f(d_1)f(d_2)$$ 两个式子对比一下，得到 $f(a)f(b)=f(ab)$，所以 $f(n)$ 也是积性函数。归纳法证毕。 ------------ 莫比乌斯函数：定义 $\sum_{d|n}\mu (d)=\varepsilon(n)$ 的函数 $\mu$ 称莫比乌斯函数。 **性质1**：$\mu$ 是积性函数。 **证明**：在开头的前置里证明过这个结论。因为 $\varepsilon$ 是积性函数，所以 $\mu$ 也是积性函数。 **性质2**：设 $p$ 为质数，则： $$\mu(p^k)=\begin{cases} 1 & k=0\\ -1 & k=1\\ 0 & k>1 \end{cases}$$ **证明**：$\sum_{i=0}^k\mu(p^i)=\varepsilon(p^k)$ 代入易得。 **性质3**：设 $n$ 有 $k$ 个质因子，则： $$\mu(n)=\begin{cases} 1 & n=1\\ 0 & n\text{ 有质因子次数大于 $1$}\\ (-1)^k & \text{其他情况} \end{cases}$$ **证明**：用前两个性质易得。 **性质4**：$\mu*1=\varepsilon$。 ------------ 莫比乌斯反演两个公式： 1. $g(n)=\sum_{d|n}f(n)\iff f=\mu*g$。 2. $g(n)=\sum_{n|d}f(n)\iff f(n)=\sum_{n|d}\mu*f$，注意这个公式的 $d$ 是一直变大直到 $+\infty$ 的。 只证明一：由狄利克雷卷积的结合律、交换律： $$g(n)=\sum_{d|n}f(n)=f*1$$ 所以 $$\mu*g=\mu*(f*1)=(\mu*1)*f=\varepsilon*f=f$$ 显然这个等式从哪个方向都可以推出来。 # 【应用】 1. 注意 $\sum_{d|n}\mu(d)=\varepsilon(n)$。也很有用。 [ZAP-Queries](https://www.luogu.com.cn/problem/P3455) > 求 $\displaystyle\sum_{i=1}^a\sum_{j=1}^b[gcd(a,b)=d]$，$a,b,d\le 5e4$。有多组测试数据，最多 $5e4$ 组。 ### 常用变形： $gcd(a,b)=d\iff gcd(\frac{a}{d},\frac{b}{d})=1$，然后用 $\sum_{d|n}\mu(d)=\varepsilon(gcd(\frac{a}{d},\frac{b}{d}))$ 转化。 回到正题。 $$\text{原式}=\displaystyle\sum_{i=1}^a\sum_{j=1}^b[d|i]\times [d|j]\times [gcd(\frac{i}{d},\frac{j}{d})=1]$$ 既然 $i,j$ 是 $d$ 的倍数，我们不如直接枚举 $i'=i/d,j'=j/d =\displaystyle\sum_{i'=1}^{[\frac{a}{d}]}\sum_{j'=1}^{[\frac{b}{d}]}[gcd(i',j')=1]

莫比乌斯函数性质：\sum_{d|n}\mu(d)=\varepsilon(n)

=\displaystyle\sum_{i'=1}^{[\frac{a}{d}]}\sum_{j'=1}^{[\frac{b}{d}]}\sum_{k|gcd(i',j')}\mu(k) =\displaystyle\sum_{i'=1}^{[\frac{a}{d}]}\sum_{j'=1}^{[\frac{b}{d}]}\sum_{k|i',k|j'}\mu(k)

同样，既然 i',j' 是 k 的倍数，不如先枚举 k。记 A=[\frac{a}{d}],B=[\frac{b}{d}]。

=\displaystyle\sum_{k=1}^{\min(A,B)}\sum_{i''=1}^{[\frac{A}{k}]}\sum_{j''=1}^{[\frac{B}{k}]}\mu(k) =\displaystyle\sum_{k=1}^{\min(A,B)}[\frac{A}{k}][\frac{B}{k}]\mu(k)

发现 [\frac{A}{k}][\frac{B}{k}] 的取值是 O(\sqrt A) 的，可以整除分块。

为什么是 O(\sqrt A) 的？把 [\frac{A}{k}] 的函数图像画出来，是阶梯式下降的，每一层阶梯就是一个取值区间。而 [\frac{B}{k}] 的函数图像最多把 [\frac{A}{k}] 再多分割出一倍。

整除分块后，就是对一个区间的 \mu 求和，可以用前缀和。

复杂度 O(\sqrt A)。

公约数的和

\sum_{i=1}^n\sum_{j=i+1}^ngcd(i,j),n\le 2\times 10^6

这里有一个经典 trick: 枚举 gcd 然后统计个数。

\sum_{g=1}^ng\times \sum_{i=1}^{[\frac{n}{g}]}\sum_{j=i+1}^{[\frac{n}{g}]}[gcd(i,j)=1]

记 G=[\frac{n}{g}]。注意这里又可以用 \varepsilon(gcd(i,j)) 了。

\sum_{g=1}^ng\times \sum_{i=1}^G\sum_{j=i+1}^G\sum_{d|i,d|j}\mu(d)

先枚举 d。

\sum_{g=1}^ng\sum_{d=1}^G\sum_{i=1}^{[\frac{G}{d}]}\sum_{j=1}^{[\frac{G}{d}]}\mu(d) \sum_{g=1}^ng\sum_{d=1}^G\mu(d)\cdot\sum_{i=1}^{[\frac{G}{d}]}\sum_{j=1}^{[\frac{G}{d}]}1 \sum_{g=1}^ng\sum_{d=1}^G\mu(d)\cdot\frac{1}{2}[\dfrac{G}{d}]([\dfrac{G}{d}-1])

对 [\dfrac{G}{d}] 进行数论分块。

复杂度：对于每一个 g，复杂度是 O(\sqrt G)=O(\sqrt{\dfrac{n}{g}}) 的。

总复杂度 O(\displaystyle\sum_{g=1}^n\sqrt{\frac{{n}}{{g}}})=O(\sqrt n+\sqrt \frac{n}{2}+\cdots)<O(n+\dfrac{n}{2}+\cdots)=O(n\log n).

Crash 的数字表格

经典题。求 \displaystyle\sum_{i=1}^n\sum_{j=1}^mlcm(i,j)，n,m\le 10^7。

不妨 n\le m。

\text{原式}=\sum_{i=1}^n\sum_{j=1}^m\dfrac{i\cdot j}{gcd(i,j)}=\sum_{g=1}^{n}\sum_{i=1}^{[n/g]}\sum_{j=1}^{[m/g]}\dfrac{ijg^2}{g}\cdot[gcd(i,j)=1] =\sum_{g=1}^ng\sum_{i=1}^{[n/g]}\sum_{j=1}^{[m/g]}ij\cdot\sum_{d|i,d|j}\mu(d)

记 [n/g]=N,[m/g]=M.

=\sum_{g=1}^ng\sum_{d=1}^N\mu(d)\sum_{i=1}^{[N/d]}\sum_{j=1^{}}^{[M/d]}ij

其中 \sum_{i=1}^{[N/d]}\sum_{j=1^{}}^{[M/d]}ij 是可以 O(1) 求得的。

记 f(x,y)=\sum_{d=1}^x\mu(d)\sum_{i=1}^{[x/d]}\sum_{j=1}^{[y/d]}ij。

则 \text{原式}=ans(n)=\displaystyle\sum_{g=1}^ng\cdot f([\dfrac{n}{g}],[\dfrac{m}{g}]).

在求 ans(n) 的时候用整除分块 [\dfrac{n}{g}],[\dfrac{m}{g}]；在求 f() 的时候再整除分块。

复杂度 O(\sqrt n\cdot \sqrt N)<O(n).

.