M_sea

莫比乌斯反演学习笔记
式子如果有$g(x)=\sum\limits_{d|x}f(d)$,那么可以得到$f(x)=\sum\limits...
扫描右侧二维码阅读全文
09
2019/02

莫比乌斯反演学习笔记

式子

  • 如果有$g(x)=\sum\limits_{d|x}f(d)$,那么可以得到$f(x)=\sum\limits_{d|x}\mu\left(\frac{x}{d}\right)g(d)$。
  • 如果有$g(x)=\sum\limits_{x|d}^nf(d)$,那么可以得到$f(x)=\sum\limits_{x|d}^n\mu\left(\frac{d}{x}\right)g(d)$。

栗子

求 $\displaystyle\sum_{i=1}^n\sum\limits_{j=1}^m[gcd(i,j)=d]$ 。为了方便,假设 $n\leq m$ 。

设 $\displaystyle f(x)=\sum_{i=1}^n\sum_{j=1}^m[gcd(i,j)=x]$,$\displaystyle g(x)=\sum\limits_{x|d}^n f(d)$ 。

首先有

$$\displaystyle\begin{aligned}g(x)&=\sum_{i=1}^n\sum_{j=1}^m[x|\gcd(i,j)]\\&=\sum_{i=1}^{n/x}\sum_{j=1}^{m/x}[1|\gcd(i,j)]\\&=\lfloor\frac{n}{x}\rfloor\lfloor\frac{m}{x}\rfloor\end{aligned}$$

那么考虑莫比乌斯反演得到 $f$

$$\displaystyle\begin{aligned}f(x)&=\sum_{x|d}^n\mu(\frac{d}{x})g(d)\\&=\sum\limits_{i=1}^{n/x}\mu(i)g(ix)\\&=\sum\limits_{i=1}^{n/x}\mu(i)\lfloor\frac{n}{x}\rfloor\lfloor\frac{m}{x}\rfloor\end{aligned}$$

筛出 $\mu$ 的前缀和后数论分块即可。

更多的栗子

链接

最后修改:2019 年 06 月 25 日 08 : 35 PM

4 条评论

  1. smy

    Orz

  2. Qihoo360

    Orz

  3. xgzc

    Orz

    1. M_sea
      @xgzc

      Orz

发表评论