「学习笔记」莫比乌斯反演进阶篇

杜教筛

杜教筛可以快速求一些积性函数的前缀和。假设我们要求 $S(n) = \sum_{i = 1}^{n} f(i)$，杜教筛方法如下：

$$\begin {align*} & \sum_{i = 1}^{n} (f * g)(i) = \sum_{i = 1}^{n} g(i) S(\lfloor \frac{n}{i} \rfloor) \\ \Leftrightarrow \ & g(1) S(n) = \sum_{i = 1}^{n} (f * g)(i) + \sum_{i = 2}^{n} g(i) S(\lfloor \frac{n}{i} \rfloor) \end {align*}$$

对于积性函数 $f$，如果能找到积性函数 $g$，使得 $g, (f * g)$ 的前缀和都容易计算，那么我们就可以先用线性筛预处理出 $S(1), S(2), \cdots, S(\text{lim})$，然后使用整除分块和记忆化搜索计算 $S(n)$ $(n > \text{lim})$。当 $\text{lim} = n^{\frac{2}{3}}$ 时，算法的复杂度为 $O(n ^ {\frac{2}{3}})$，实际上 $\text{lim}$ 取得更大一点会更优。

例子：求 $\mu$ 的前缀和时，我们可以取 $g = 1$，这样 $(f * g) = \epsilon$，而 $1, \epsilon$ 的前缀和都可以快速计算。

YY 的 GCD

「Luogu 2257」YY 的 GCD

题目描述

$T$ 次询问 $n, m$，求：

$$\sum_{i = 1}^{n} \sum_{j = 1}^{m} [\gcd(i, j) \in P]$$

其中 $P$ 表示素数集合。

数据范围：$T \le 10^4, n, m \le 10^7$。

思路分析

设数论函数 $p(n)$ 满足当 $n$ 为素数时 $p(n) = 1$，否则 $p(n) = 0$。那么答案为：

$$\begin {align*} & \sum_{i = 1}^{n} \sum_{j = 1}^{m} [p(\text{gcd}(i, j))] \\ = & \sum_{k = 1}^{\min(n, m)} p(k) \sum_{i = 1}^{\lfloor \frac{n}{k} \rfloor} \sum_{j = 1}^{\lfloor \frac{m}{k} \rfloor} [(i, j) = 1] \\ = & \sum_{k = 1}^{\min(n, m)} p(k) \sum_{i = 1}^{\lfloor \frac{n}{k} \rfloor} \sum_{j = 1}^{\lfloor \frac{m}{k} \rfloor} \sum_{t | i, j} \mu(t) \\ = & \sum_{t = 1}^{n} \mu(t) \sum_{k = 1}^{\lfloor \frac{n}{t} \rfloor} p(k) \lfloor \frac{n}{kt} \rfloor \lfloor \frac{m}{kt} \rfloor \\ = & \sum_{i = 1}^{n} \lfloor \frac{n}{i} \rfloor \lfloor \frac{m}{i} \rfloor \sum_{d | i} \mu(d) p(\frac{i}{d}) \\ \end {align*}$$

我们记 $f(n) = \sum_{d | n} \mu(d) p(\frac{n}{d})$，考虑枚举 $\frac{n}{d}$，这样就可以 $O(n \log \log n)$ 预处理出 $f(1), f(2), \cdots, f(n)$。然后用整除分块回答每组询问即可。时间复杂度 $O(n \log \log n + T \sqrt n)$。

代码实现

#include <bits/stdc++.h>

Siyuan GCD

「LOJ 6686」Stupid GCD

题目描述

给定 $n$，求：

$$\sum_{i = 1}^{n} \gcd(\sqrt[3]{i}, i)$$

数据范围：$n \le 10^{30}$。

思路分析

见我的博客：「LOJ 6686」Stupid GCD（数论）

代码实现

#include <bits/stdc++.h>

下面原本写了 4 道题的题解，然后因为 bug 没掉了，所以这里引用黄队的博客中较重要的两题，并稍作修改。

密码解锁

「Luogu 5348」密码解锁

题目描述

已知：

$$\sum_{d|x,x\le n}f(x)=\mu(d)$$

求 $f(m)$。

数据范围：$m\le 10^9,\dfrac{n}{m}\le 10^9$。

思路分析

由莫比乌斯反演推论可以得到：

$$\begin{split}f(m)=&\sum_{m|i,i\le n}\mu(i)\mu\left(\frac{i}{m}\right)\\=&\sum_{i=1}^{\left\lfloor\frac{n}{m}\right\rfloor}\mu(im)\mu\left(i\right)\\=&\sum_{i=1}^{\left\lfloor\frac{n}{m}\right\rfloor}\mu^2(i)\mu(m)[i\perp m]\\=&\mu(m)\sum_{i=1}^{\left\lfloor\frac{n}{m}\right\rfloor}\mu^2(i)[i\perp m]\end{split}$$

考虑把这个和式做一个递归：

$$\begin{split} S(n,k)=&\sum_{i=1}^n\mu^2(i)[i\perp k]\\ =&\sum_{i=1}^n\mu^2(i)\sum_{d|i,d|k}\mu(d)\\ =&\sum_{d|k}\mu(d)\sum_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\mu^2(id)\\ =&\sum_{d|k}\mu^3(d)\sum_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\mu^2(i)[i\perp d]\\ =&\sum_{d|k}\mu(d)S\left(\left\lfloor\frac{n}{d}\right\rfloor,d\right) \end{split}$$

递归边界为 $S(n,1)=\sum_{i=1}^n\mu^2(i)$。我们考虑 $\mu^2(i)$ 的贡献。当且仅当 $i$ 不含平方及以上的因子时，$\mu^2(i)=1$，否则 $\mu^2(i)=0$。

因此我们要求 $[1, n]$ 中无平方因子的数的个数。那么考虑容斥，用整体减掉含有平方因子的数：

$$\begin{split} & \sum_{i=1}^n\mu^2(i)=n+\sum_{i=2}^n\mu(i)\left\lfloor \frac{n}{i^2} \right\rfloor\\ = & \sum_{i=1}^n\mu(i)\left\lfloor \frac{n}{i^2} \right\rfloor=\sum_{i=1}^\sqrt{n}\mu(i)\left\lfloor \frac{n}{i^2} \right\rfloor \end{split}$$

$\mu(i)$ 是容斥系数。我们记忆化计算 $S$ 即可，时间复杂度不超过 $O(\sqrt{\frac{n}{m}} \sigma_0(m))$，可以通过。

代码实现

#include <bits/stdc++.h>

FSF’s Game

「HDU 4944」FSF’s Game

题目描述

给定 $n$，求：

$$\sum_{i=1}^n\sum_{j=i}^n\sum_{k|i,k|j}\frac{ij}{\gcd\left(\frac{i}{k},\frac{j}{k}\right)}$$

数据范围：$T,n\le 5\times 10^5$。

思路分析

$$\begin{split} &\sum_{i=1}^n\sum_{j=i}^n\sum_{k|i,k|j}\frac{ij}{\gcd\left(\frac{i}{k},\frac{j}{k}\right)}\\ =&\sum_{k=1}^nk^2\sum_{i=1}^{\left\lfloor\frac{n}{k}\right\rfloor}\sum_{j=i}^{\left\lfloor\frac{n}{k}\right\rfloor}\operatorname{lcm}(i,j) \end{split}$$

设 $f(n)=\sum_{i=1}^n\sum_{j=i}^n\operatorname{lcm}(i,j)=\sum_{j=1}^n\sum_{i=1}^j\operatorname{lcm}(i,j)$。

设 $g(n)=\sum_{i=1}^n\gcd(n,i)$。那么可以用两两配对的思路反演得到：

$$g(n)=\frac{1}{2}n\left[\left(\sum_{d|n}d\cdot \varphi(d)\right)-1\right]+n$$

那么我们做一个 $g(n)$ 的前缀和就得到了 $f(n)$。现在原式化简为了：

$$F(n)=\sum_{k=1}^nk^2f\left(\left\lfloor\frac{n}{k}\right\rfloor\right)$$

发现对于 $f(i)$，它对区间 $[ij, (i + 1)j - 1]$ 中的 $F$ 有 $f(i) \times j^2$ 的贡献。枚举 $i, j$，使用前缀和优化来预处理即可，时间复杂度 $O(n \log n)$。

代码实现

#include <bits/stdc++.h>