莫比乌斯反演

前置知识-OI Wiki

莫比乌斯函数 $\mu$

$$ \mu(n)= \begin{cases} 1&n=1\\ 0&n\text{ 含有平方因子}\\ (-1)^k&k\text{ 为 }n\text{ 的本质不同质因子个数}\\ \end{cases} $$

当 $x⊥y$ ,

如果其中一个有平方因子,$\mu(x)*\mu(y)=0=\mu(xy)$ 。

如果两数都不含平方因子,$\mu(x)*\mu(y)=(-1)^{k_x+k_y}=\mu(xy)$。

所以 $\mu$ 是个积性函数。

性质:

$$ \sum_{d\mid n}\mu(d)= \begin{cases} 1&n=1\\ 0&n\neq 1\\ \end{cases} $$

证明:

令 $n=\prod\limits_{i=1}^kp_i^{c_i},n'=\prod\limits_{i=1}^kp_i$ 。

显然有 $\sum\limits_{d|n}\mu(d)=\sum\limits_{d|n'}\mu(d)$ ,因为枚举平方因子是无意义的。

那么这等价于在 $k$ 个数里面选 0 个 即 $\mu(1)$ ,贡献是 1,选 1 个,贡献是 -1,选 2 个,贡献是 1 ,选 $t$ 个,贡献是 $(-1)^t$ ,也就是 $\sum\limits_{i=0}^k\dbinom{k}{i}(-1)^i=(1-1)^k=[k==0]$。

当 k=0 时,n=1。

于是就有 $[n==1]\,↔\,\sum_{d|n}\mu(d)$ ,那么罪恶的东西要来了...

我们都知道,莫比乌斯反演最喜欢的就是 gcd,那就可以把 $[\gcd(i,j)=1]$ 替换为 $\sum_{d|\gcd(i,j)}\mu(d)$ 。

那么就可以:

$$ \begin{align} &\sum_{i=1}^n\sum_{j=1}^n[\gcd(i,j)=1]\\ =&\sum_{i=1}^n\sum_{j=1}^n\sum_{d|\gcd(i,j)}\mu(d)\\ =&\sum_{d=1}^n\sum_{i=1}^n\sum_{j=1}^n[d|i][d|j]\mu(d)\\ =&\sum_{d=1}^n\mu(d)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}1\\ =&\sum_{d=1}^n\mu(d)\lfloor\frac{n}{d}\rfloor\lfloor\frac{n}{d}\rfloor \end{align} $$

于是预处理 $\mu$ ,再每个询问整除分块,就可以做到 $\mathcal O(n+T\sqrt{n})$ 了。

莫比乌斯反演

真正的反演。

$f(n)=\sum_{d|n}g(d)\,↔\,g(n)=\sum_{d|n}\mu(d)f(\frac{n}{d})\\$

证明:

$$ \begin{align} &\sum_{d|n}\mu(d)f(\frac{n}{d})\\ =&\sum_{d|n}\mu(d)\sum_{k|\frac{n}{d}}g(k)\\ =&\sum_{k|n}g(k)\sum_{d|\frac{n}{k}}\mu(d)\\ =&g(n) \end{align} $$

虽然不会用,但结论就是这样...下面是几道例题。

$(n,m\leq10^5)$

$$ \begin{align} ans&=\sum^n_{i=1}\sum^m_{j=1}(2*\gcd(i,j)-1)\\ &=2*\sum^n_{i=1}\sum^m_{j=1}\gcd(i,j)-n*m\\ S&=\sum^n_{i=1}\sum^m_{j=1}\gcd(i,j)\\ ans&=2S-n*m \end{align} $$

$$ \begin{align} f(d)&=\sum^n_{i=1}\sum^m_{j=1}[\gcd(i,j)=d]\\ &=\sum^{\lfloor\frac{n}{d}\rfloor}_{i=1}\sum^{\lfloor\frac{m}{d}\rfloor}_{j=1}[\gcd(i,j)=1]\\ &=\sum_{d'}\mu(d')\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}[d'|i]\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}[d'|j]\\ &=\sum_{d'}\mu(d')\lfloor\frac{n}{dd'}\rfloor\lfloor\frac{m}{dd'}\rfloor \end{align} $$

$$ \begin{align} S&=\sum_{d}f(d)*d\\ &=\sum_{d=1}^nd*\sum_{d'=1}^{\lfloor\frac{n}{d}\rfloor}\mu(d')\lfloor\frac{n}{dd'}\rfloor\lfloor\frac{m}{dd'}\rfloor\\ \end{align}\\ $$

求 $S$ 时两段数论分块,可以做到 $O(\sqrt{n}*\sqrt{n})=O(n)$ ,但 $T$ 组数据时总时间复杂度达到 $O(n+Tn)$,不太优秀。

对于求$\sum^n_{i=1}\sum^m_{j=1}\gcd(i,j)$,其实还有另一种更高效的方法。

证明:$\sum_{d|n}\phi(d)=n$

设 $f(n)=\sum_{d|n}\phi(d)$。

设 $a⊥b$ ,则 $\phi(a)*\phi(b)=\phi(ab)$,那么

$$ \begin{align} &f(a)*f(b)\\ =&\sum_{i|a}\phi(i)\sum_{j|b}\phi(b)\\ =&\sum_{i|a}\sum_{j|b}\phi(i)*\phi(j)\\ =&\sum_{i|a}\sum_{j|b}\phi(i*j)\\ =&\sum_{d|ab}\phi(d)\\ =&f(ab) \end{align} $$

即 $f$ 也是积性函数,那么

$$ \begin{align} &f(p^k)\\ =&\sum_{i=0}^k\phi(p^i)\\ =&1+(p-1)+(p^2-p)+...+(p^k-p^{k-1})\\ =&p^k \end{align} $$

于是设 $n=\prod_{i=1}^mp_i^{k_i}$,$f(n)=\prod_{i=1}^mf(p_i^{k_i})=\prod_{i=1}^mp_i^{k_i}=n$。

证毕。

回到求 $\sum^n_{i=1}\sum^m_{j=1}\gcd(i,j)$ 身上,把 $\gcd(i,j)$ 换成 $f(\gcd(i,j))$ ,那么

$$ \begin{align} &\sum^n_{i=1}\sum^m_{j=1}\gcd(i,j)\\ =&\sum^n_{i=1}\sum^m_{j=1}\sum_{d|\gcd(i,j)}\phi(d)\\ =&\sum_d\phi(d)\sum_{i=1}^n[d|i]\sum_{j=1}^m[d|j]\\ =&\sum_d\phi(d)\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor \end{align} $$

这样虽然单次询问需要线性筛 $\phi$ ,时间复杂度 $O(n+\sqrt{n})$,

但在 $T$ 组数据时可以做到 $O(n+T\sqrt{n})$,比上面方法的 $O(n+Tn)$ 更优。

利用了欧拉函数 $\sum_{d|n}\phi(d)=n$ 的性质,也称这种方法叫欧拉反演。

$T$ 组数据,求

$$ \sum^n_{i=1}\sum_{j=1}^n(i+j)^K\mu^2(\gcd(i,j))\gcd(i,j) $$

$(T=10^4,n\leq10^7)$

$$ \begin{align} &\sum_d\mu^2(d)* d*\sum_{i=1}^n\sum_{j=1}^n(i+j)^K[\gcd(i,j)=d]\\ =&\sum_d\mu^2(d)*d*d^K*\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}(i+j)^K[\gcd(i,j)=1]\\ =&\sum_d\mu^2(d)*d*d^K*\sum_{d'}\mu(d')d'^K\sum_{i=1}^{\lfloor\frac{n}{dd'}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{dd'}\rfloor}(i+j)^K\\ =&\sum_TT^K\sum_{d|T}\mu^2(d)*\mu(\frac{T}{d})*d*\sum_{i=1}^{\lfloor\frac{n}{T}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{T}\rfloor}(i+j)^K\\ &设\, S(n)=\sum_{i=1}^{n}\sum_{j=1}^{n}(i+j)^K\\ &显然有\, S_n=\sum_{s=2}^n(s-1)*s^K+\sum_{s=n+1}^{2n}(2n-s+1)*s^K\\ &线性筛预处理完全积性函数\quad p_n=n^k\,并记录前缀和,那么就可以线性预处理出S_n\\ &设\, f_n=\sum_{d|n}\mu^2(d)\mu(\frac{n}{d})*d,是积性函数可以线性筛\\ 上式=&\sum_Tf(T)T^KS(\lfloor\frac{n}{T}\rfloor)\\ &f(T)T^K可以做前缀和,后面的整除分块\\ &O(n+T\sqrt{n}) \end{align} $$

最后修改:2021 年 03 月 25 日 07 : 42 PM