系统写一下莫反。
莫反公式
其中 $\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)$。