莫反笔记

· · 个人记录

谈一点自己对于莫反的初步的理解。

感觉这个玩意非常的套路，网上给的那两个莫反的式子好像没什么用，其实最重要的还是 \mu 函数的这个性质：

\sum_{d|n}\mu(d)=\left[n=1\right]

那这玩意什么情景下可以用？就是题目让你求的式子里带着或者有一部分可以转化为这样的式子：

\sum_{i=1}^a\sum_{j=1}^b\left[\gcd(i,j)=x\right]

当然 i 和 j 也不一定要从 1 开始枚举，但是那只需要简单的容斥就可以转化到这个式子，那么现在就来看看这个式子该怎么求。

不妨设 a\le b，首先把式子中 i，j 的枚举范围都除以一个 x，然后原式就等于：

\sum_{i=1}^{\left\lfloor\frac{a}{x}\right\rfloor} \sum_{j=1}^{\left\lfloor\frac{b}{x}\right\rfloor}[\gcd(i,j)=1]

然后上开头提到的式子：

\sum_{i=1}^{\left\lfloor\frac{a}{x}\right\rfloor} \sum_{i=1}^{\left\lfloor\frac{b}{x}\right\rfloor}\sum_{d|\gcd(i,j)}\mu(d)

为了继续化简，把后面那个式子拆一下：

\sum_{i=1}^{\left\lfloor\frac{a}{x}\right\rfloor} \sum_{i=1}^{\left\lfloor\frac{b}{x}\right\rfloor}\sum_{d=1}^{\lfloor\frac{a}{x}\rfloor}\mu(d)\times [d|\gcd(i,j)]

然后你会发现此时的 \mu(d) 与 i，j 已经没有了半毛钱关系，于是改变一下枚举顺序，并把 \mu(d) 拽到前面：

\sum_{d=1}^{\lfloor\frac{a}{x}\rfloor}\mu(d)\sum_{i=1}^{\left\lfloor\frac{a}{x}\right\rfloor} \sum_{i=1}^{\left\lfloor\frac{b}{x}\right\rfloor} [d|\gcd(i,j)]

然后后面两个 \sum 就可以不要了：

\sum_{d=1}^{\lfloor\frac{a}{x}\rfloor}\mu(d)\lfloor \frac{a}{x\!\times\! d}\rfloor\lfloor \frac{b}{x\!\times\! d}\rfloor

然后这个东西现在已经可以线性求了，配合整除分块可以到 O(\sqrt n)。 后面要是再乘个式子可以先预处理，然后前缀和