莫比乌斯反演
狄利克雷卷积
定义:
$(f*g)(n)=\sum_{d\mid n}f(d)g(n/d)$
很显然满足交换律和结合律。
积性函数
为积性函数的有:
$I (n)$ (或$1(n)$ ),恒等于1，所以叫恒等函数
$\epsilon (n)$ (或者$e(n)$ ),当且仅当 $n=1$ 时，其值为 $1$,否则为 $0$,其满足($e*f=f$)(因此为狄利克雷卷积的单位元)
$id(n)=n$ 为单位函数。
以上为完全积性函数。
完全积性函数:
对于任意整数 $a$ 和 $b$ 满足 $f(ab)=f(a)f(b)$
以及：
$\varphi (n)$ ,欧拉函数，小于 $n$ 的整数中与 $n$ 互质的数的个数。
$\mu (n)$ ,莫比乌斯函数，接下来我们重点讲，暂且不介绍。
积性函数:
对于两个整数 $a,b$ ，满足 $(a,b)=1$ ，则 $f(ab)=f(a)f(b)$
虽然没有完全积性函数优美，但是这很好吧，这可以吧。(
然后研究一下这个积性函数的性质。
- 积性函数 $f$,总满足 $f(1)=1$
这个易证了，$f(1)=f(1)f(1)$
- 两积性函数之积为积性函数。
这个稍微难一点。
证明:
定义两个积性函数 $f,g$ ,其卷积为 $G=f*g$.
任取两个互质的数 $a,b$
$G(a)G(b)$
$=\sum_{d\mid a}f(d)g(b/d)*\sum_{t\mid b}f(t)g(b/t)$
$=\sum_{d\mid a}\sum_{t\mid b}f(d)g(a/d)f(t)g(b/t)$
$=\sum_{dt\mid ab}f(dt)g(ab/dt)$
$=G(ab)$
$Q.E.D.$
- 积性函数的逆也是积性函数
归纳证明，就不证明了
莫比乌斯函数
引入
对于两个函数 $f,F$,满足 $F(n)=\sum_{d\mid n}(1*f(d) )$
等价于
\[F=I *f\]然后有
\[f=I^{-1}*F\]我们把 $I^{-1}$ 称为 $\mu$ 莫比乌斯函数。
也就有 $f=\mu *F$
定义:
然后有个性质：
- $(\mu *1)=e$
从定义出发易证。互逆的两个函数卷起来是单位元。
- $\varphi *1=id$ ,然后 $\varphi=\mu *id$
由 $\varphi *1=id$，且 $\mu *1=e$
得
\[\varphi * 1 *\mu=id*\mu\]即
\[\varphi=\mu *id\]然后证一下 $\varphi *1=id$
想了解可以参考 OI wiki
莫比乌斯反演
进入正题。
- 嵌入式莫比乌斯反演
由 $\mu *1=e$ 得 $\sum_{d\mid n}\mu(d)=[n=1]$
因为 $[n\mid m][n/m=1]=[n=m]$
所以有 $[n\mid m]\sum_{d\mid (n/m)}\mu(d)=[n=m]$ (因为只有当n=1的时候这个玩意才满足)
可以这么转换。
- $\sum_{d\mid (i,j)}\mu (d)=[(i,j)=1]$
因为 $\sum_{d\mid (i,j)}\mu (d)=e(gcd(i,j) )$,易证
然后你肯定是要会算莫比乌斯函数的，开筛！
这个我们之前的博客中有，于是不多说了。筛
变换形式
- $F(n)=\sum_{d\mid n}f(d) \Leftrightarrow f(n)=\sum_{d\mid n}\mu(d)F(n/d)$
本质还是
\[F=1*f \Leftrightarrow f=F*I^{-1} \Leftrightarrow f=F*\mu\]数论分块
用来计算形如 $\sum_{i=1}^{n}f(i)g(\lfloor \frac{n}{i} \rfloor)$ 的和式。
我们再单独来讲这个 数论分块
我们推个式子：
\[ans=\sum_{i=1}^{n}\sum_{j=1}^{m}[(i,j)=1]\] \[=\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{d\mid (i,j)}\mu(d)\] \[=\sum_{d=1}^{min\{n,m\}}\mu(d)\sum_{d\mid i}^{n}\sum_{d\mid j}^{m}1\] \[=\sum_{d=1}^{min\{n,m\}}\mu(d)\lfloor n/d \rfloor \lfloor m/d \rfloor\]这个式子我们可以 $O(n)$ 的算。
接下来我们用数论分块处理，达到 $O(\sqrt{n})$
总之莫反的题就是分为反演和分块，学懂了还是挺套路的。