莫比乌斯反演是数论中的重要内容,对于一些函数 $math_inline$f(n)$math_inline$ ,如果很难直接求出它的值,而容易求出其倍数和或约数和 $math_inline$g(n)$math_inline$ ,那么可以通过莫比乌斯反演简化运算,求得 $math_inline$f(n)$math_inline$ 的值。
开始学习莫比乌斯反演前我们需要一些前置知识:积性函数、Dirichlet卷积、莫比乌斯函数
数论分块与整除相
引理 1
$math_inline$ \forall a,b,c\in\mathbb{Z},\left\lfloor\frac{a}{bc}\right\rfloor=\left\lfloor\frac{\left\lfloor\frac{a}{b}\right\rfloor}{c}\right\rfloor $math_inline$略证
$math_inline$ \begin{split} &\frac{a}{b}=\left\lfloor\frac{a}{b}\right\rfloor+r(0\leq r<1)\\\\ \Rightarrow &\left\lfloor\frac{a}{bc}\right\rfloor =\left\lfloor\frac{a}{b}\cdot\frac{1}{c}\right\rfloor =\left\lfloor \frac{1}{c}\left(\left\lfloor\frac{a}{b}\right\rfloor+r\right)\right\rfloor =\left\lfloor \frac{\left\lfloor\frac{a}{b}\right\rfloor}{c} +\frac{r}{c}\right\rfloor =\left\lfloor \frac{\left\lfloor\frac{a}{b}\right\rfloor}{c}\right\rfloor \end{split} $math_inline$引理 2
$math_inline$ \forall{n} \in N, \left | \left\{ \lfloor \frac{n}{d} \rfloor \mid d \in N \right\}\right| \leq \lfloor 2\sqrt{n} \rfloor $math_inline$$math_inline$|V|$math_inline$ 表示集合 $math_inline$V$math_inline$ 的元素个数
略证
对于 $math_inline$d\leq\lfloor\sqrt{n}\rfloor$math_inline$ , $math_inline$\lfloor \frac{n}{d}\rfloor$math_inline$ 有 $math_inline$\lfloor\sqrt{n}\rfloor$math_inline$ 种取值
对于 $math_inline$d>\lfloor\sqrt{n}\rfloor$math_inline$ ,有 $math_inline$\lfloor \frac{n}{d}\rfloor\leq\lfloor\sqrt{n}\rfloor$math_inline$ ,也只有 $math_inline$\lfloor\sqrt{n}\rfloor$math_inline$ 种取值
综上得证
数论分块
数论分块的过程大概如下:考虑含有 $math_inline$\lfloor\frac{n}{i}\rfloor$math_inline$ 的求和式子( $math_inline$n$math_inline$ 为常数)
对于任意一个 $math_inline$i(i\leq n)$math_inline$ ,我们需要找到一个最大的 $math_inline$j(i\leq j\leq n)$math_inline$ ,使得 $math_inline$\lfloor\frac{n}{i}\rfloor=\lfloor\frac{n}{j}\rfloor$math_inline$
而 $math_inline$j=\left\lfloor\frac{n}{\left\lfloor\frac{n}{i}\right\rfloor}\right\rfloor$math_inline$
略证
$math_inline$ \begin{split} &\left\lfloor\frac{n}{i}\right\rfloor \leq \frac{n}{i}\\ \Rightarrow &\left\lfloor\frac{n}{ \left\lfloor\frac{n}{i}\right\rfloor }\right\rfloor \geq \left\lfloor\frac{n}{ \frac{n}{i} }\right\rfloor = \left\lfloor i \right\rfloor=i \\ \Rightarrow &i\leq \left\lfloor\frac{n}{ \left\lfloor\frac{n}{i}\right\rfloor }\right\rfloor \end{split} $math_inline$即 $math_inline$j=\left\lfloor\frac{n}{\left\lfloor\frac{n}{i}\right\rfloor}\right\rfloor$math_inline$
利用上述结论,我们每次以 $math_inline$[i,j]$math_inline$ 为一块,分块求和即可
积性函数
定义
若 $math_inline$\gcd(x,y)=1$math_inline$ 且 $math_inline$f(xy)=f(x)f(y)$math_inline$ ,则 $math_inline$f(n)$math_inline$ 为积性函数。
性质
若 $math_inline$f(x)$math_inline$ 和 $math_inline$g(x)$math_inline$ 均为积性函数,则以下函数也为积性函数
$math_inline$ \begin{aligned} h(x)&=f(x^p)\\ h(x)&=f^p(x)\\ h(x)&=f(x)g(x)\\ h(x)&=\sum_{d\mid x}f(d)g(\frac{x}{d}) \end{aligned} $math_inline$例子
- 单位函数: $math_inline$\epsilon(n)=[n=1]$math_inline$
- 恒等函数: $math_inline$\operatorname{id}_k(n)=n^k\operatorname{id}_{1}(n)$math_inline$ 通常记做 $math_inline$\operatorname{id}(n)$math_inline$
- 常数函数: $math_inline$1(n)=1$math_inline$
- 除数函数: $math_inline$\sigma_{k}(n)=\sum_{d\mid n}d^{k}\sigma_{0}(n)$math_inline$ 通常简记做 $math_inline$\operatorname{d}(n)$math_inline$ 或 $math_inline$\tau(n)$math_inline$ , $math_inline$\sigma_{1}(n)$math_inline$ 通常简记做 $math_inline$\sigma(n)$math_inline$
- 欧拉函数: $math_inline$\varphi(n)=\sum_{i=1}^n [\gcd(i,n)=1]$math_inline$
- 莫比乌斯函数: $math_inline$\mu(n) = \begin{cases}1 & n=1 \\ 0 & \exists d:d^{2} \mid n \\ (-1)^{\omega(n)} & otherwise\end{cases}$math_inline$ 其中 $math_inline$\omega(n)$math_inline$ 表示 $math_inline$n$math_inline$ 的本质不同质因子个数,是一个加性函数
Dirichlet卷积
定义
定义两个数论函数 $math_inline$f,g$math_inline$ 的Dirichlet卷积为
$math_inline$ (f*g)(n)=\sum_{d\mid n}f(d)g(\frac{n}{d}) $math_inline$性质
Dirichlet卷积满足交换律和结合律
其中 $math_inline$\varepsilon$math_inline$ 为Dirichlet卷积的单位元(任何函数卷 $math_inline$\epsilon$math_inline$ 都为其本身)
例子
$math_inline$ \begin{aligned} \varepsilon=\mu*1&\Leftrightarrow\varepsilon(n)=\sum_{d\mid n}\mu(d)\\ d=1*1&\Leftrightarrow d(n)=\sum_{d\mid n}1\\ \sigma=d*1&\Leftrightarrow\varepsilon(n)=\sum_{d\mid n}d\\ \varphi=\mu*\text{ID}&\Leftrightarrow\varphi(n)=\sum_{d\mid n}d\cdot\mu(\frac{n}{d}) \end{aligned} $math_inline$莫比乌斯函数
定义
$math_inline$\mu$math_inline$ 为莫比乌斯函数
性质
莫比乌斯函数不但是积性函数,还有如下性质:
$math_inline$ \mu(n)= \begin{cases} 1&n=1\\ 0&n\text{ 含有平方因子}\\ (-1)^k&k\text{ 为 }n\text{ 的本质不同质因子个数}\\ \end{cases} $math_inline$证明
$math_inline$ \varepsilon(n)= \begin{cases} 1&n=1\\ 0&n\neq 1\\ \end{cases} $math_inline$其中 $math_inline$\displaystyle\varepsilon(n)=\sum_{d\mid n}\mu(d)$math_inline$ 即 $math_inline$\varepsilon=\mu*1$math_inline$
设 $math_inline$\displaystyle n=\prod_{i=1}^k{p_i}^{c_i},n'=\prod_{i=1}^k p_i$math_inline$
那么 $math_inline$\displaystyle\sum_{d\mid n}\mu(d)=\sum_{d\mid n'}\mu(d)=\sum_{i=0}^k C_k^i\cdot(-1)^k$math_inline$
根据二项式定理,易知该式子的值在 $math_inline$k=0$math_inline$ 即 $math_inline$n=1$math_inline$ 时的值为 $math_inline$1$math_inline$ 否则为 $math_inline$0$math_inline$ ,这也同时证明了 $math_inline$\sum_{d|n}{\mu(d)}=[n=1]$math_inline$
补充结论
反演推论: $math_inline$\displaystyle [gcd(i,j)=1] \Leftrightarrow\sum_{d\mid\gcd(i,j)}\mu(d)$math_inline$
- **直接推导:**如果看懂了上一个结论,这个结论稍加思考便可以推出:如果 $math_inline$\gcd(i,j)=1$math_inline$ 的话,那么代表着我们按上个结论中枚举的那个 $math_inline$n$math_inline$ 是 $math_inline$1$math_inline$ ,也就是式子的值是 $math_inline$1$math_inline$ ,反之,有一个与 $math_inline$[\gcd(i,j)=1]$math_inline$ 相同的值:0
- **利用 $math_inline$\varepsilon$math_inline$ 函数:**根据上一结论, $math_inline$[\gcd(i,j)=1]\Rightarrow \varepsilon(\gcd(i,j))$math_inline$ ,将 $math_inline$\varepsilon$math_inline$ 展开即可。
线性筛
由于 $math_inline$\mu$math_inline$ 函数为积性函数,因此可以线性筛莫比乌斯函数(线性筛基本可以求所有的积性函数,尽管方法不尽相同)。
Code
void getMu() {
mu[1] = 1;
for (int i = 2; i <= n; ++i) {
if (!flg[i]) p[++tot] = i, mu[i] = -1;
for (int j = 1; j <= tot && i * p[j] <= n; ++j) {
flg[i * p[j]] = 1;
if (i % p[j] == 0) {
mu[i * p[j]] = 0;
break;
}
mu[i * p[j]] = -mu[i];
}
}
}
拓展
$math_inline$\varphi*1=\text{ID}\text{(ID 函数即 } f(x)=x\text{)}$math_inline$将 $math_inline$n$math_inline$ 分解质因数: $math_inline$\displaystyle n=\prod_{i=1}^k {p_i}^{c_i}$math_inline$
首先,因为 $math_inline$\varphi$math_inline$ 是积性函数,故只要证明当 $math_inline$n'=p^c$math_inline$ 时 $math_inline$\displaystyle\varphi*1=\sum_{d\mid n'}\varphi(\frac{n'}{d})=\text{ID}$math_inline$ 成立即可。
因为 $math_inline$p$math_inline$ 是质数,于是 $math_inline$d=p^0,p^1,p^2,\cdots,p^c$math_inline$
易知如下过程
$math_inline$ \begin{aligned} \varphi*1&=\sum_{d\mid n}\varphi(\frac{n}{d})\\ &=\sum_{i=0}^c\varphi(p^i)\\ &=1+p^0\cdot(p-1)+p^1\cdot(p-1)+\cdots+p^{c-1}\cdot(p-1)\\ &=p^c\\ &=\text{ID}\\ \end{aligned} $math_inline$该式子两侧同时卷 $math_inline$\mu$math_inline$ 可得 $math_inline$\displaystyle\varphi(n)=\sum_{d\mid n}d\cdot\mu(\frac{n}{d})$math_inline$
莫比乌斯反演
公式
设 $math_inline$f(n),g(n)$math_inline$ 为两个数论函数
如果有 $math_inline$f(n)=\sum_{d\mid n}g(d)$math_inline$
那么有 $math_inline$g(n)=\sum_{d\mid n}\mu(d)f(\frac{n}{d})$math_inline$
证明
**暴力计算:** $math_inline$\sum_{d\mid n}\mu(d)f(\frac{n}{d})=\sum_{d\mid n}\mu(d)\sum_{k\mid \frac{n}{d}}g(k)=\sum_{k\mid n}g(k)\sum_{d\mid \frac{n}{k}}\mu(d)=g(n)$math_inline$
用 $math_inline$\displaystyle\sum_{d\mid n}g(d)$math_inline$ 来替换 $math_inline$f(\dfrac{n}{d})$math_inline$ ,再变换求和顺序。最后一步转为的依据: $math_inline$\displaystyle\sum_{d\mid n}\mu(d)=[n=1]$math_inline$
因此在 $math_inline$\dfrac{n}{k}=1$math_inline$ 时第二个和式的值才为 $math_inline$1$math_inline$ 。此时 $math_inline$n=k$math_inline$ ,故原式等价于 $math_inline$\displaystyle\sum_{k\mid n}[n=k]\cdot g(k)=g(n)$math_inline$
运用卷积:
原问题为:已知 $math_inline$f=g*1$math_inline$ ,证明 $math_inline$g=f*\mu$math_inline$
易知如下转化: $math_inline$f*\mu=g*1*\mu\Rightarrow f*\mu=g$math_inline$ (其中 $math_inline$1*\mu=\varepsilon$math_inline$ )
莫比乌斯反演拓展
对于数论函数 $math_inline$f,g$math_inline$ 和完全积性函数 $math_inline$t$math_inline$ 且 $math_inline$t(1)=1$math_inline$ :
$math_inline$ f(n)=\sum_{i=1}^nt(i)g\left(\left\lfloor\frac{n}{i}\right\rfloor\right)\\ \Leftrightarrow g(n)=\sum_{i=1}^n\mu(i)t(i)f\left(\left\lfloor\frac{n}{i}\right\rfloor\right) $math_inline$我们来证明一下:
$math_inline$ \begin{eqnarray} &&g(n)=\sum_{i=1}^n\mu(i)t(i)f\left(\left\lfloor\frac{n}{i}\right\rfloor\right)\\ &=&\sum_{i=1}^n\mu(i)t(i) \sum_{j=1}^{\left\lfloor\frac{n}{i}\right\rfloor}t(j) g\left(\left\lfloor\frac{\left\lfloor\frac{n}{i}\right\rfloor}{j}\right\rfloor\right)\\ &=&\sum_{i=1}^n\mu(i)t(i) \sum_{j=1}^{\left\lfloor\frac{n}{i}\right\rfloor}t(j) g\left(\left\lfloor\frac{n}{ij}\right\rfloor\right)\\ &=&\sum_{T=1}^n \sum_{i=1}^n\mu(i)t(i) \sum_{j=1}^{\left\lfloor\frac{n}{i}\right\rfloor}[ij=T] t(j)g\left(\left\lfloor\frac{n}{T}\right\rfloor\right) &&\text{【先枚举 ij 乘积】}\\ &=&\sum_{T=1}^n \sum_{i|T}\mu(i)t(i) t\left(\frac{T}{i}\right)g\left(\left\lfloor\frac{n}{T}\right\rfloor\right) &&\text{【}\sum_{j=1}^{\left\lfloor\frac{n}{i}\right\rfloor}[ij=T] \text{对答案的贡献为 1,于是省略】}\\ &=&\sum_{T=1}^ng\left(\left\lfloor\frac{n}{T}\right\rfloor\right) \sum_{i|T}\mu(i)t(i)t\left(\frac{T}{i}\right)\\ &=&\sum_{T=1}^ng\left(\left\lfloor\frac{n}{T}\right\rfloor\right) \sum_{i|T}\mu(i)t(T) &&\text{【t 是完全积性函数】}\\ &=&\sum_{T=1}^ng\left(\left\lfloor\frac{n}{T}\right\rfloor\right)t(T) \sum_{i|T}\mu(i)\\ &=&\sum_{T=1}^ng\left(\left\lfloor\frac{n}{T}\right\rfloor\right)t(T) \varepsilon(T) &&\text{【}\mu\ast 1= \varepsilon\text{】}\\ &=&g(n)t(1) &&\text{【当且仅当 T=1,}\varepsilon(T)=1\text{时】}\\ &=&g(n) && \square \end{eqnarray} $math_inline$解法二:
转化一下,可以将式子写成
$math_inline$ \begin{eqnarray} &&\sum_{d=1}^{n}\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}ijd\cdot[gcd(i,j)=1]\\ &=&\sum_{d=1}^{n}d\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}ij\sum_{t\mid gcd(i,j)}\mu(t)\\ &=&\sum_{d=1}^{n}d\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}ij\sum_{t=1}^{\lfloor\frac{n}{d}\rfloor}\mu(t)[t\mid gcd(i,j)]\\ &=&\sum_{d=1}^{n}d\sum_{t=1}^{\lfloor\frac{n}{d}\rfloor}t^2 \mu(t)\sum_{i=1}^{\lfloor\frac{n}{td}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{td}\rfloor}ij[1\mid gcd(i,j)]\\ &=&\sum_{d=1}^{n}d\sum_{t=1}^{\lfloor\frac{n}{d}\rfloor}t^2 \mu(t)\sum_{i=1}^{\lfloor\frac{n}{td}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{td}\rfloor}ij \end{eqnarray} $math_inline$容易知道
$math_inline$ \sum_{i=1}^{n}\sum_{j=1}^{m}ij=\frac{n(n+1)}{2}\cdot \frac{m(m+1)}{2} $math_inline$设 $math_inline$sum(n,m)=\sum_{i=1}^{n}\sum_{j=1}^{m}ij$math_inline$ ,继续接着前面的往下推
$math_inline$ \begin{eqnarray} &&\sum_{d=1}^{n}d\sum_{t=1}^{\lfloor\frac{n}{d}\rfloor}t^2 \mu(t)\sum_{i=1}^{\lfloor\frac{n}{td}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{td}\rfloor}ij\\ &=&\sum_{d=1}^{n}d\sum_{t=1}^{\lfloor\frac{n}{d}\rfloor}t^2 \mu(t)\cdot sum(\lfloor\frac{n}{td}\rfloor,\lfloor\frac{m}{td}\rfloor)\\ &=&\sum_{T=1}^{n}sum(\lfloor\frac{n}{T}\rfloor,\lfloor\frac{m}{T}\rfloor)\sum_{d\mid T}d\cdot (\frac{T}{d})^2\mu(\frac{T}{d})\\ &=&\sum_{T=1}^{n}sum(\lfloor\frac{n}{T}\rfloor,\lfloor\frac{m}{T}\rfloor)(T\sum_{d\mid T}d\cdot\mu(d)) \end{eqnarray} $math_inline$这时我们只要对每个 $math_inline$T$math_inline$ 预处理出 $math_inline$T\sum_{d\mid T}d\cdot\mu(d)$math_inline$ 的值就行了,考虑如何快速求解
设 $math_inline$f(n)=\sum_{d\mid n}d\cdot\mu(d)$math_inline$
实际上 $math_inline$f$math_inline$ 可以用线性筛筛出,具体的是
$math_inline$ f(n)= \begin{cases} 1-n &,n\in primes \\ f(\frac{x}{p}) &,p^2\mid n\\ f(\frac{x}{p})\cdot f(p) &,p^2\nmid n \end{cases} $math_inline$其中 $math_inline$p$math_inline$ 表示 $math_inline$n$math_inline$ 的最小质因子
总时间复杂度 $math_inline$O(n+\sqrt{n})$math_inline$