0%

莫反

系统写一下莫反。

莫反公式

其中 $\mu(n)$ 为莫比乌斯函数,

且该函数为积性函数,即若 $n\perp m$ 则有 $\mu(nm)=\mu(n)\cdot \mu(m)$。证明是显然的。

特别的,我们有

我们不妨设 $f(n)=\displaystyle\sum_{d|n}\mu(d)$,显然可得 $f(n)$ 也是积性函数,因此设 $n=p_1^{\alpha_1}p_2^{\alpha_2}\dots p_k^{\alpha_k}$,则有

由于 $\forall n>1$ 一定 $\exists 1\le i\le k$ 使得 $\alpha_i>0$,所以


上面的莫反公式其实等价于

莫反常见套路

使用反演公式

更换求和顺序

然后可以将 $d$ 放到开头去枚举,然而如何计算后面的?

考虑 $d|\gcd(i,j)\Leftrightarrow d|i,d|j$。因此对于一个确定的 $d$,在原式子中有 $\mu(d)$ 项的 $(i,j)$ 一定都是 $d$ 的倍数。因此我们枚举 $d$ 的时候,后面的 $i,j$ 可以直接枚举 $d$ 倍数:

个人感觉本质上,假设原来的求和顺序是 $d\in P(i,j,\dots)$ 那么我们就要找一个 $d$ 推到 $i,j,\dots$ 的关系,并且以此写出新的求和式子。

合并枚举项

假设现在有一个式子

你发现可以暴力枚举 $p$ 后预处理出来后面的东西,时间复杂度 $O(n)$。但是你想更快怎么办?

注意到这个式子中有两个变量:$p,d$,而且后面有 $pd$。因此可以想到令 $T=pd$ 然后直接枚举 $T$。

注意到 $\displaystyle \sum_{\substack{p|T\\p\text{ is prime}}}\mu\left(\dfrac Tp\right)$ 可以被预处理,具体的对每个素数枚举倍数再加贡献,时间复杂度是 $n$ 乘素数倒数和,也就是 $O(n\ln\ln n)$。

例题

板子题水,不写了

P3704

默认 $n\le m$。题目就是让求

考察指数上的部分,是

套路地枚举 $T=kd$。那么式子变为

里面这东西可以预处理,因此时间复杂度 $O(t\sqrt n\log n)$。

为什么这个式子是对的。

考虑一个 $\mathrm{fib}_d$ 会被计算几次,显然所有 $d$ 的倍数都会对它有贡献,对于一个倍数 $kd$,指数上的贡献就是 $\mu(k)\cdot\left\lfloor\dfrac n{kd}\right\rfloor\left\lfloor\dfrac m{kd}\right\rfloor$。由于 $k$ 的取值就是 $1\sim\left\lfloor\dfrac n{d}\right\rfloor$,因此 $\mathrm{fib}_d$ 的指数就是 $\displaystyle\sum_{k=1}^{\lfloor\frac nd\rfloor}\mu(k)\cdot\left\lfloor\dfrac n{kd}\right\rfloor\left\lfloor\dfrac m{kd}\right\rfloor$,和原式相同。

P1829

默认 $n\le m$,则将原式变换为

我们把目光放在后半部分上,记 $\displaystyle s(n,m)=\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=1]ij$,则有

我们发现形如 $\displaystyle f(n)=\sum_{i=1}^ni=\dfrac{n(n+1)}{2}$,因此 $s(n,m)$ 可以通过数论分块在 $O(\sqrt n)$ 的时间复杂度内求出。

回过头来,原式就是

再利用一次数论分块,总时间复杂度 $O(n)$。因此加上预处理后复杂度为 $O(n+m)$。

P6156

给定 $n,k$,求

我们定义 $\displaystyle S(n)=\sum_{i=1}^n\sum_{j=1}^n(i+j)^k$,记 $\displaystyle F(n)=\sum_{i=1}^ni^k$、$\displaystyle G(n)=\sum_{i=1}^nF(i)$。考虑求解这个式子:

考虑到 $n^k$ 可以线性筛。具体的在 $p$ 位置快速幂,在合数位置求解,时间复杂度为 $O(n)$。因此 $S(n)$ 可以预处理后 $O(1)$ 求解。

其实到这里就可以两次整除分块 $O(n)$ 求解了……


接下来看原式子:

套路地枚举 $dt$,则有

发现框内是一个 Dirichlet 卷积的形式,由于其中 $d\mu^2(d)$ 和 $\mu\left(\dfrac nd\right)$ 都是积性函数,因此可知 $\displaystyle f(n)=\sum_{d|n}d\mu^2(d)\cdot\mu\left(\dfrac nd\right)$ 同样也是积性函数。因此我们在线性筛的同时求解 $f(n)$。

考虑 $f(p^\alpha)$ 的取值。由于式子中有 $\mu(d)$ 因此可以从 $\alpha$ 的大小来考虑。

  • $\alpha=0$:即为 $f(1)=1$。
  • $\alpha=1$:即为 $f(p)=p\cdot\mu(1)+1\cdot\mu(p)=p-1$。
  • $\alpha=2$:$f(p^2)=p\cdot\mu(p)=-p$。
  • $\alpha\ge3$:注意到在 $p^\alpha$ 的因子 $p^\beta$ 中,$\beta$ 和 $\alpha-\beta$ 至少有一个大于等于 $2$,因此此时 $f(p^\alpha)=0$。

所以可以 $O(1)$ 求解 $f(p^\alpha)$ 的值,也就可以 $O(n)$ 筛出 $f$ 的值。

现在原式子变成了

至此可以 $O(\sqrt n)$ 求解答案。时间复杂度为 $O(n)-O(\sqrt n)$。