【听课笔记】Mobiüs反演听课笔记

主要是莫比乌斯反演这一块的听课笔记,由于记录的太长了(不会的太多了) 所以就分了一下。

反演好啊,有趣啊,不会啊!

关于 $\mu$ 的有趣证明

思考 $\mu$ 的本质,当 $n$ 含有平方因子的时候,$\mu(n)=0$;否则 $\mu(n)=(-1)^k$,其中 $k$ 是 $n$ 的本质不同质因子个数。

接下来考虑一步转化。设 $n=\sum p_i^{e_i},n’=\sum{p_i}$ 。那么有

瞎反演记录

那大概使用来热身的。

  • 反演1
  • 反演2

各种题

SPOJ LCMSUM

求 $\sum _{i=1}^n \mathrm{lcm}(n,i)$ .

$n\leq 10^6,T\leq 10^5$

草,这真是个神仙题。考虑 $\rm lcm$ 自然是要转化成

那么考虑快速计算这个东西。一个自然的想法考虑能不能筛,筛就要求必须要是狄利克雷卷积的形似。想要转化过去的话必须是对 $n$ 的因子求和,于是想到要按照 $\gcd $ 分类,那么 $\gcd(n,i)=d$ 的 $i$ 总共有 $\varphi(\frac{n}{d})$ 个。

但是注意到分类之后,由于每一项都带有 $i$ 所以无法快速计算。考虑一个性质,$\gcd(n,k)=\gcd(n,n- k)$ 。那么就是:

发现后面那一项就可以快速求和了:

那么答案就是

就可以快速筛出来了。复杂度 $O(n)-O(1)$ 。

HDU 4944

$n,T\leq 5\times 10^5$

首先看到 $d$ 知道要提出来

发现对于 $f(n)=\sum_{i=1}^n\sum_{j=i}^n \mathrm{lcm}(i,j)$ 可以转化成

也就是上面LCMSUM里面求得的东西。于是就可以整除分块做了。复杂度 $O(n+T\sqrt n)$ 。

注意到,预处理的时候还可以计算每个 $d$ 对于每个 $n$ 的贡献。具体一点,考虑本质上对于每个 $n$,$d$ 的贡献都是 $d^{2} f\left(\left\lfloor\frac{n}{d}\right\rfloor\right)$ ,至多有 $\left\lfloor\frac{n}{d}\right\rfloor$ 种不同的取值,且每个取值对应的 $n$ 的区间是连续的。于是就用一些差分技巧差分一下这个修改。注意到这个的复杂度是调和级数的,所以总复杂度 $O(n\ln n)-O(1)$ 。

其实这里还有一点题,但是因为觉得很有趣就单拿出来了。