许久不发博客，近两个月来先是区域赛和EC，然后又是紧锣密鼓的考试，确实没时间写东西。这几天复习了下Mobius反演，感觉比以前有了更深的认识，记在这里。
首先这里是 popoqqq神犇的ppt
题目主要来自于这个PPT。
BZOJ 2440
这个感觉PPT里面讲的挺详细的，二分答案之后容斥算出答案以内的个数就行了。至于容斥：所有的数-( \( 2^2\)的所有倍数+\(3^2\)的所有倍数 +\(5^2\) 的所有倍数 )+(\(6^2\)的所有倍数+…)-(…)…
这样可以发现每一项前面的系数和Mobius函数是相同的，所以有: \[ ans=\sum_i^{\sqrt{n}} \mu(i) \lfloor{\frac{n}{i^2} \rfloor} \]
这一题就当用来练手了。
BZOJ 2301
Mobius反演的经典应用，用来求某段区间中\(gcd(x,y)=k\)的数对个数。
这题以前是写过的，这里重新写了下。
\[ 我们设f(d)为 gcd(x,y)=d的数对个数 \ \ \ \ (1 \leq x,y \leq n) \] \[ 再设F(d)为\ d\ |\ gcd(x,y)的数对个数 \ \ \ \ (1\leq x,y \leq n) \] 很明显 \[ F(x)=\sum_{x|d} f(d) \] 根据反演 \[ f(x)=\sum_{x|d} \mu(\frac{d}{x})F(d) \] 我们知道\(F(d)=\lfloor \frac{n}{d} \rfloor \lfloor \frac{n}{d} \rfloor \) 代回去即可得 \[ f(x)=\sum_{x|d} \mu(\frac{d}{x}) \lfloor \frac{n}{d} \rfloor \lfloor \frac{n}{d} \rfloor \] 即 \[ f(x)=\sum_{k} \mu(k) \lfloor \frac{n}{kx} \rfloor \lfloor \frac{n}{kx} \rfloor \] 分块求解即可
BZOJ 3529
这一题我们设\(F(x)为x的因子和 \)，我们要求 \[ \sum_{i,j}F(gcd(i,j)) \mod 2^{31} \] 我们设\(g(d)为gcd(i,j)=d的对数\)，所以得到 \[ ans=\sum_d{F(d)g(d)} \] 利用上一题的思路，我们可以得到： \[ ans=\sum_d \sum_{d|D} F(d) \mu(\frac{D}{d})\lfloor \frac{n}{D} \rfloor \lfloor \frac{m}{D} \rfloor \] 交换求和的变量 \[ ans=\sum_D^{min(n,m)} \lfloor \frac{n}{D} \rfloor \lfloor \frac{m}{D} \rfloor \sum_{d|D} F(d)\mu(\frac{D}{d}) \] 对询问排序后可以动态维护后面那一段的前缀和，离线处理即可。
BZOJ 2154
这一题感觉算是这里面比较难的一题了，需要比较高的公式化简水平（也有可能是我太菜？）
题目大意是给你一个(n,m)的表格，每个格子里面是\(lcm(i,j)\)的值。现在要求这整个表的和。
即求 \[ ans=\sum_i^n\sum_j^m lcm(i,j) \]
我们首先把lcm化成gcd的形式： \[ ans=\sum_i^n\sum_j^m \frac{i*j}{gcd(i,j)} \]
我们设\(gcd(i,j)=d\) 于是就有 \[ \sum_i^n\sum_j^m \frac{i*j}{d} \] 考虑枚举d，有
\[ \sum_d^{min(n,m)} \sum_{d|i}^n \sum_{d|j}^m \frac{i*j}{d} \]
设\(i=xd,j=yd \)，有 \[ ans=\sum_d^{min(n,m)} \sum_x^{ \lfloor \frac{n}{d} \rfloor} \sum_y^{\lfloor \frac{m}{d} \rfloor } \frac{xd*yd}{d} \]
\[ =\sum_d^{min(n,m)} d \sum_x^{ \lfloor \frac{n}{d} \rfloor} \sum_y^{\lfloor \frac{m}{d} \rfloor } x*y\ \ \ \ \ \ \ (gcd(x,y)=1) \]
我们利用\(\mu\)函数的性质\(\sum_{c} \mu(c) \)当c不等于1的时候该式=0，当c等于1的时候该式等于1。 我们利用这个性质可以把不互质的x,y筛掉。于是我们设
\[ F(n,m)=\sum_x^n\sum_y^m x*y \ \ \ \ (gcd(x,y)=1) \]
该式可以变为
\[ \begin{align} F(n,m) & =\sum_x^n\sum_y^m(x·y·\sum_{c|gcd(x,y)} \mu(c)) \
& = \sum_c^{min(n,m)}\mu(c)\sum_{c|x}^n\sum_{c|y}^m x·y \
& = \sum_c^{min(n,m)}\mu(c)·c^2 \sum_x^{\lfloor \frac{n}{c} \rfloor}\sum_y^{\lfloor \frac{m}{c} \rfloor} x·y \end{align} \]
注意到后面一段可以\(O(1)\)直接求和，所以该函数可以分块\(O(\sqrt{n})\)求得，对于ans: \[ ans=\sum_d^{min(n,m)} d F(\lfloor \frac{n}{d} \rfloor,\lfloor \frac{m}{d} \rfloor ) \] 所以ans也可以分块\(O(\sqrt{n})\)求得，所以总的时间复杂度为\(O({n})\)
至此，问题解决。
当然到这里为止还不是最优的方法，还可以继续化简，这里实在是不想继续敲公式了…贴个大神的地址把…
关于反演还是有不少东西的，感觉现在还只是在比较初级的阶段而已，这几个题算是趁热打铁，写完之后记在这里，以后有了更深的认识再回来改吧（当然也可能再写一个…）。