莫比乌斯反演学习笔记
Warriors_Cat
2020-08-21 18:37:11
某种意义上说是个草稿纸（
算了算了还是认真写吧（
部分内容参考 [OI-Wiki 莫比乌斯反演](https://oi-wiki.org/math/mobius/)
## 1. 数论分块
经典例题，求：
$$\sum_{i=1}^n \left\lfloor \dfrac{n}{i} \right\rfloor$$
首先搞一个引理：
> 对于任意 $i \in [1, n] \cup \mathbb{Z}$，$\max_{\left\lfloor \frac{n}{j} \right\rfloor=\left\lfloor \frac{n}{i} \right\rfloor, j \in \mathbb{Z}}j = \left\lfloor \dfrac{n}{\left\lfloor \dfrac{n}{i} \right\rfloor} \right\rfloor$，而且 $j \in [i, n]$。
证明：
显然 $j \le n$。先证明 $j=\left\lfloor \dfrac{n}{\left\lfloor \dfrac{n}{i} \right\rfloor} \right\rfloor$ 时后面的成立。
$$j = \left\lfloor \dfrac{n}{\left\lfloor \dfrac{n}{i} \right\rfloor} \right\rfloor \ge \left\lfloor \dfrac{n}{\dfrac{n}{i}} \right\rfloor =\left\lfloor i \right\rfloor = i$$
记 $\left\lfloor \dfrac{n}{i} \right\rfloor=k$。
$$\left\lfloor \dfrac{n}{j} \right\rfloor=k\iff k \le \dfrac{n}{j} < k+1 \iff \dfrac{1}{k+1} < \dfrac{j}{n} \le \dfrac{1}{k}\iff \dfrac{n}{k+1} < j \le \dfrac{n}{k}$$
又因为 $j \in \mathbb{Z}$，所以 $j_{max} = \left\lfloor \dfrac{n}{\left\lfloor \dfrac{n}{i} \right\rfloor} \right\rfloor$。
$\mathcal{Q.E.D.}$
于是我们可以以每个 $[i, j]$ 分块，对于每一块求值。
更形象化的：
```cpp
i 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
n/i 24 12 8 6 4 4 3 3 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1
n/(n/i) 1 2 3 4 6 6 8 8 12 12 12 12 24 24 24 24 24 24 24 24 24 24 24 24
```
具体实现：
```cpp
for(int i = 1, j; i <= n; i = j + 1){
j = n / (n / i);
ans += n / i * (j - i + 1);
}
```
但有时候我们还会有二维限制，不过代码差不多：
```cpp
if(n > m) swap(n, m);
for(int i = 1, j; i <= n; i = j + 1){
j = min(n / (n / i), m / (m / i));
ans += calc(i, j);//具体题目具体实现
}
```
## 2. 积性函数
若函数 $f(n)$ 满足 $f(1) = 1$ 且 $\forall x, y \in \mathbb{N}^*, \gcd(i, j)=1$ 都有 $f(xy)=f(x)f(y)$，那么 $f(x)$ 为积性函数。
若函数 $f(n)$ 满足 $f(1) = 1$ 且 $\forall x, y \in \mathbb{N}^*$ 都有 $f(xy)=f(x)f(y)$，那么 $f(x)$ 为完全积性函数。
常见积性函数：
单位函数：$\epsilon(n) = [n = 1]$
恒等函数：$\operatorname{id}_k(n) = n^k$，其中 $\operatorname{id}_1(n)$ 通常记为 $\operatorname{id}(n)$
常数函数：$1(n)=1$
除数函数：$\sigma_k(n)=\sum_{d|n}d^k$，其中 $\sigma_0(n)$ 通常记为 $d(n)$，$\sigma_1(n)$ 通常记为 $\sigma(n)$
欧拉函数：$\varphi(n)=\sum_{i=1}^n [\gcd(i, n)=1]$
莫比乌斯函数：$\mu(n)=\begin{cases}1&n=1\\0&\exists d > 1: d^2 | n\\(-1)^{\omega(n)} &\operatorname{otherwise}\end{cases}$，其中 $\omega(n)$ 表示 $n$ 本质不同的质因子个数。
其中前三个函数是完全积性函数，后三个函数是积性函数。
## 3. 狄利克雷卷积
定义两个数论函数 $f, g$ 的狄利克雷卷积为
$$(f * g)(x)=\sum_{d|x}f(d)g(\dfrac{x}{d})$$
通常简单表示为 $h = f * g$。
狄利克雷函数满足交换律，结合律，分配律，$f * \epsilon = f$。
具体例子：
$$\epsilon = \mu * 1 \iff \epsilon(n) = \sum_{d|n}\mu(n)$$
$$d = 1 * 1 \iff d(n) = \sum_{d|n}1$$
$$\sigma = \operatorname{id} * 1 \iff \sigma(n)=\sum_{d|n}d$$
$$\varphi = \mu * \operatorname{id} \iff \varphi(n)=\sum_{d|n}d
\cdot \mu(\dfrac{n}{d})$$
中间两个显然成立，第一个稍后证明，现在证明 $\varphi * 1 = \operatorname{id}$，证明如下：
记 $n=\prod_{i=1}^kp_i^{\alpha_i}$，$n'=p_i^{\alpha_i}$。由于 $\varphi$ 是个积性函数，那么只要证明对每一个 $n'$ 都满足 $\varphi * 1 = \operatorname{id}$ 即可。
$$\begin{aligned}\varphi * 1 &= \sum_{d|n}\varphi(d) \\&=\sum_{i=0}^{\alpha}\varphi(p^i) \\&= 1+\sum_{i=0}^{\alpha - 1}p^i\cdot(p-1)\\&= p^\alpha \\ &= \operatorname{id} \end{aligned}$$
$$\mathcal{Q.E.D.}$$
那么 $\varphi * 1 * \mu = \operatorname{id} * \mu$
即 $\varphi = \operatorname{id} * \mu$
## 4. 莫比乌斯函数
$$\mu(n)=\begin{cases}1&n=1\\0&\exists d > 1: d^2 | n\\(-1)^{\omega(n)}&\operatorname{otherwise}\end{cases}$$
其性质有 $\mu * 1 = \epsilon$。证明如下：
显然当 $n=1$ 时 $\sum_{d|n}\mu(d)=1$。
当 $n\neq 1$ 时，记 $n = \prod_{i=1}^k p_i^{\alpha_i}$，$m=\prod_{i=1}^kp_i$。
那么 $\sum_{d|n}\mu(d)=\sum_{d|m}\mu(d)=\sum_{i=0}^k C_k^i\cdot (-1)^i=[1 + (-1)]^k =0$。
于是 $\sum_{d|n}\mu (d)=[n=1]$，即 $\mu * 1 = \epsilon$。
$\mathcal{Q.E.D.}$
由于 $\mu$ 是一个积性函数，所以我们可以用线性筛筛出 $\mu$ 的值，具体实现如下：
```cpp
inline void seive(int n){
mu[1] = 1;//积性函数定义
for(int i = 2; i <= n; ++i){
if(!vis[i]) mu[i] = -1, pri[++len] = i;//质数显然为 -1
for(int j = 1; j <= len && i * pri[j] <= n; ++j){
vis[i * pri[j]] = 1;
if(i % pri[j] == 0){ mu[i * pri[j]] = 0; break; }//平方因子为 0
else mu[i * pri[j]] = -mu[i];//取相反
}
}
}
```
## 5. 莫比乌斯反演
现有两个数论函数 $f(n), g(n)$。
若 $f(n) = \sum_{d|n}g(d)$，则 $g(n)=\sum_{d|n}\mu(d)f(\dfrac{n}{d})$。
若 $f(n) = \sum_{n|d}g(d)$，则 $g(n)=\sum_{n|d}\mu(\dfrac{d}{n})f(d)$。
仅证明第一个式子，第二个式子同理，证明如下：
原式等价于 $f = g * 1$。
那么 $f * \mu = g * 1 * \mu$。
又因为 $1 * \mu = \epsilon$，所以 $f * \mu = g * \epsilon = g$。
$\mathcal{Q.E.D.}$
常用式子：
$$f = g * 1 \iff g = f * \mu$$
$$\epsilon=\mu * 1$$
$$\varphi = \operatorname{id} * \mu \iff \varphi * 1 = \operatorname{id}$$
## 6.~~草稿纸~~具体题目
越到后面可能推式子过程会越简略，请见谅（
以下题目默认 $n \le m$，$N$ 为 $n, m$ 上限。
一. $T$ 组询问，每组询问给定 $n, m$，求
$$\sum_{i=1}^n\sum_{j=1}^m[\gcd(i, j) = 1]$$
解：
运用 $\mu * 1 = \epsilon$ 可得
$$\text{原式}=\sum_{i=1}^n\sum_{j=1}^m\sum_{d|{(i, j)}}\mu(d)$$
调换求和顺序，先枚举 $d$ 可得
$$\begin{aligned}\text{原式}&=\sum_{d=1}^n\mu(d)\sum_{i=1}^{\left\lfloor \frac{n}{d} \right\rfloor}\sum_{j=1}^{\left\lfloor \frac{m}{d} \right\rfloor}1\\&= \sum_{d=1}^n \mu(d) \left\lfloor \frac{n}{d} \right\rfloor \left\lfloor \frac{m}{d} \right\rfloor\end{aligned}$$
线性筛预处理 $\mu(d)$ 的前缀和 + 数论分块即可，时间复杂度为 $O(N+T\sqrt{N})$。
二（[P3455](https://www.luogu.com.cn/problem/P3455) & [P2522](https://www.luogu.com.cn/problem/P2522)）. $T$ 组询问，每组询问给定 $n, m, k$，求
$$\sum_{i=1}^n\sum_{j=1}^m[\gcd(i, j) = k]$$
解：
将 $k$ 提出来：
$$\text{原式}=\sum_{i=1}^{\left\lfloor \frac{n}{k} \right\rfloor}\sum_{j=1}^{\left\lfloor \frac{m}{k} \right\rfloor}[\gcd(i, j)=1]$$
然后就和上一题一样了，最终化简成：
$$\text{原式}=\sum_{d=1}^{\left\lfloor \frac{n}{k} \right\rfloor}\mu(d)\left\lfloor \frac{n}{kd} \right\rfloor\left\lfloor \frac{m}{kd} \right\rfloor$$
线性筛预处理 $\mu(d)$ 的前缀和 + 数论分块即可，时间复杂度为 $O(N+T\sqrt{N})$。
代码实现：
```cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
inline int read(){
int x = 0, f = 1; char ch = getchar();
while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar(); }
while(ch >= '0' && ch <= '9'){ x = x * 10 + (ch ^ 48); ch = getchar(); }
return x * f;
}
const int N = 50010;
int t, n, m, k, mu[N], pri[N], len;
bool vis[N];
inline void seive(){
mu[1] = 1;
for(int i = 2; i <= N - 10; ++i){
if(!vis[i]) mu[i] = -1, pri[++len] = i;
for(int j = 1; j <= len && i * pri[j] <= N - 10; ++j){
vis[i * pri[j]] = 1;
if(i % pri[j] == 0){ mu[i * pri[j]] = 0; break; }
mu[i * pri[j]] = -mu[i];
}
}
for(int i = 1; i <= N - 10; ++i) mu[i] += mu[i - 1];
}
inline int calc(int n, int m){
if(n > m) n ^= m ^= n ^= m; int ans = 0;
for(int i = 1, j; i <= n; i = j + 1){
j = min(n / (n / i), m / (m / i));
ans += (mu[j] - mu[i - 1]) * (n / i) * (m / i);
}
return ans;
}
int main(){
seive(); t = read();
while(t--){
n = read(); m = read(); k = read();
n /= k; m /= k;
printf("%d\n", calc(n, m));
}
return 0;
}
```
三. $T$ 组询问，每组询问给定 $n, m, k$，求
$$\sum_{i=1}^n\sum_{j=1}^m ij[\gcd(i, j)=k]$$
解：
将 $k$ 提出来：
$$\begin{aligned}\text{原式}&=\sum_{i=1}^{\left\lfloor \frac{n}{k} \right\rfloor}\sum_{j=1}^{\left\lfloor \frac{m}{k} \right\rfloor} k^2ij[\gcd(i, j)=1] \\ &= k^2\sum_{i=1}^{\left\lfloor \frac{n}{k} \right\rfloor}\sum_{j=1}^{\left\lfloor \frac{m}{k} \right\rfloor} ij[\gcd(i, j)=1]\end{aligned}$$
运用 $\mu * 1 = \epsilon$ 可得
$$\text{原式}=k^2\sum_{i=1}^{\left\lfloor \frac{n}{k} \right\rfloor}\sum_{j=1}^{\left\lfloor \frac{m}{k} \right\rfloor} ij\sum_{d\mid\gcd(i, j)}\mu(d)$$
调换求和顺序，先枚举 $d$ 可得
$$\text{原式}=k^2\sum_{d=1}^{\left\lfloor \frac{n}{k} \right\rfloor}\mu(d)\cdot d^2\sum_{i=1}^{\left\lfloor \frac{n}{kd} \right\rfloor}\sum_{j=1}^{\left\lfloor \frac{m}{kd} \right\rfloor}ij$$
记 $S(n, m) = \sum_{i=1}^n\sum_{j=1}^m ij$，易得 $S(n, m) = \dfrac{n(n+1)}{2}\cdot\dfrac{m(m+1)}{2}$，可 $O(1)$ 求出。
带入原式：
$$\text{原式}=k^2\sum_{d=1}^{\left\lfloor \frac{n}{k} \right\rfloor}\mu(d)\cdot d^2\cdot S(\left\lfloor \frac{n}{kd} \right\rfloor, \left\lfloor \frac{m}{kd} \right\rfloor)$$
线性筛预处理 $\mu(d)\cdot d^2$ 的前缀和 + 数论分块即可，时间复杂度为 $O(N + T\sqrt{N})$。
四（[P2398](https://www.luogu.com.cn/problem/P2398) & [P1390](https://www.luogu.com.cn/problem/P1390) & ......~~听说这题七倍经验~~）. $T$ 组询问，每次给定 $n, m$，求
$$\sum_{i=1}^n\sum_{j=1}^m\gcd(i, j)$$
解：
运用 $\varphi * 1 = \operatorname{id}$ 可得
$$\text{原式}=\sum_{i=1}^n\sum_{j=1}^m\sum_{d\mid\gcd(i, j)}\varphi(d)$$
同样调换求和顺序，先枚举 $d$ 可得：
$$\begin{aligned}\text{原式}&=\sum_{d=1}^n\varphi(d)\sum_{i=1}^{\left\lfloor \frac{n}{d} \right\rfloor}\sum_{j=1}^{\left\lfloor \frac{m}{d} \right\rfloor} 1 \\ &= \sum_{d=1}^n \varphi(d) \left\lfloor \dfrac{n}{d} \right\rfloor \left\lfloor \dfrac{m}{d} \right\rfloor\end{aligned}$$
线性筛预处理 $\varphi(d)$ 的前缀和 + 数论分块即可，时间复杂度为 $O(N + T\sqrt{N})$。
下面给出 [P2398](https://www.luogu.com.cn/problem/P2398) 的代码：
```cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define int long long
inline int read(){
int x = 0, f = 1; char ch = getchar();
while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar(); }
while(ch >= '0' && ch <= '9'){ x = x * 10 + (ch ^ 48); ch = getchar(); }
return x * f;
}
const int N = 100010;
int n, len, phi[N], pri[N], vis[N], s[N];
inline void seive(int n){
phi[1] = 1;
for(int i = 2; i <= n; ++i){
if(!vis[i]) pri[++len] = i, phi[i] = i - 1;
for(int j = 1; j <= len && i * pri[j] <= n; ++j){
int k = i * pri[j];
vis[k] = pri[j];
if(i % pri[j] == 0){
phi[k] = phi[i] * pri[j];
break;
}
phi[k] = phi[i] * (pri[j] - 1);
}
}
for(int i = 1; i <= n; ++i) s[i] = s[i - 1] + phi[i];
}
inline int sol(int n, int m){
int ans = 0; if(n > m) n ^= m ^= n ^= m;
for(int i = 1, j; i <= n; i = j + 1){
j = min(n / (n / i), m / (m / i));
ans += (s[j] - s[i - 1]) * (n / i) * (m / i);
}
return ans;
}
signed main(){
n = read();
seive(n);
printf("%lld", sol(n, n));
return 0;
}
```
五（[P1829](https://www.luogu.com.cn/problem/P1829)）. 单次询问，给定 $n, m$，求
$$\sum_{i=1}^n\sum_{j=1}^m \operatorname{lcm}(i, j)$$
解：
直接大力推导式子。
$$\begin{aligned}\text{原式}&=\sum_{i=1}^n\sum_{j=1}^m\dfrac{ij}{\gcd(i, j)} \\ &= \sum_{d=1}^n\sum_{i=1}^n\sum_{j=1}^m \dfrac{ij}{d}[\gcd(i, j)=d]\\ &= \sum_{d=1}^n\sum_{i=1}^{\left\lfloor \frac{n}{d} \right\rfloor}\sum_{j=1}^{\left\lfloor \frac{m}{d} \right\rfloor}dij[\gcd(i, j)=1]\\&=\sum_{d=1}^nd\sum_{i=1}^{\left\lfloor \frac{n}{d} \right\rfloor}\sum_{j=1}^{\left\lfloor \frac{m}{d} \right\rfloor}ij[\gcd(i, j)=1]\end{aligned}$$
运用“三”可得
$$\text{原式}=\sum_{d=1}^n d\sum_{k=1}^{\left\lfloor \frac{n}{d} \right\rfloor}\mu(k)\cdot k^2\cdot S(\left\lfloor \frac{n}{kd} \right\rfloor, \left\lfloor \frac{m}{kd} \right\rfloor)$$
其中 $S(n, m)=\sum_{i=1}^n\sum_{j=1}^m ij = \dfrac{n(n+1)}{2}\cdot\dfrac{m(m+1)}{2}$
线性筛预处理 $\mu(k)\cdot k^2$ 的前缀和，然后数论分块套数论分块即可，时间复杂度为 $O(n + m)$。
代码实现：
```cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
inline int read(){
int x = 0, f = 1; char ch = getchar();
while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar(); }
while(ch >= '0' && ch <= '9'){ x = x * 10 + (ch ^ 48); ch = getchar(); }
return x * f;
}
const int N = 10000010, mod = 20101009;
int n, m, pri[N], mu[N], len; bool vis[N];
inline void seive(int n){
mu[1] = 1;
for(int i = 2; i <= n; ++i){
if(!vis[i]) mu[i] = -1, pri[++len] = i;
for(int j = 1; j <= len && i * pri[j] <= n; ++j){
vis[i * pri[j]] = 1;
if(i % pri[j] == 0){ mu[i * pri[j]] = 0; break; }
mu[i * pri[j]] = -mu[i];
}
}
for(int i = 1; i <= n; ++i) mu[i] = (mu[i - 1] + 1ll * i * i % mod * (mu[i] + mod) % mod) % mod;
}
inline int cal(int n, int m){
return (1ll * n * (n + 1) / 2 % mod) * (1ll * m * (m + 1) / 2 % mod) % mod;
}
inline int calc(int n, int m){
int ans = 0;
for(int i = 1, j; i <= n; i = j + 1){
j = min(n / (n / i), m / (m / i));
ans = (ans + 1ll * (mu[j] - mu[i - 1] + mod) % mod * cal(n / i, m / i) % mod) % mod;
}
return ans;
}
inline int sol(int n, int m){
int ans = 0;
for(int i = 1, j; i <= n; i = j + 1){
j = min(n / (n / i), m / (m / i));
ans = (ans + 1ll * (i + j) * (j - i + 1) / 2 % mod * calc(n / i, m / i) % mod) % mod;
}
return ans;
}
int main(){
n = read(); m = read(); if(n > m) n ^= m ^= n ^= m;
seive(m); printf("%d", sol(n, m));
return 0;
}
```
### 拓展：
有些时候，这题是多组询问，于是我们需要更加优秀的复杂度。
我们令 $T = kd$，然后枚举 $T$ 和 $d$，那么 $k$ 自然可以求得。
于是原式可以进一步化简：
$$\begin{aligned}\text{原式}&=\sum_{T=1}^n\sum_{d|T} d\cdot \mu(\dfrac{T}{d})\cdot\dfrac{T^2}{d^2}\cdot S(\left\lfloor \frac{n}{T} \right\rfloor, \left\lfloor \frac{m}{T} \right\rfloor)\\&= \sum_{T=1}^nT\sum_{d|T} \mu(d)\cdot d\cdot S(\left\lfloor \frac{n}{T} \right\rfloor, \left\lfloor \frac{m}{T} \right\rfloor) \end{aligned}$$
然后 $f(T) = T\sum_{d|T}\mu(d)\cdot d$ 是个积性函数，所以可以线性筛预处理出前缀和。具体筛法如下：
$$f(n)=\begin{cases}n(1-n)&n \in \mathbb{P}\\n\cdot f(\frac{n}{p})&p^2 \mid n \\ n\cdot f(\frac{n}{p})\cdot f(p)&p^2 \nmid n\end{cases}$$
单次询问时间复杂度就完美的从 $O(n + m)$ 变成 $O(\sqrt{n})$。
总时间复杂度为 $O(N + T\sqrt{N})$，其中 $T$ 为询问组数。
代码实现：
```cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
inline int read(){
int x = 0, f = 1; char ch = getchar();
while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar(); }
while(ch >= '0' && ch <= '9'){ x = x * 10 + (ch ^ 48); ch = getchar(); }
return x * f;
}
const int N = 10000010, mod = 20101009;
int n, m, pri[N], f[N], len; bool vis[N];
inline void seive(int n){
f[1] = 1;
for(int i = 2; i <= n; ++i){
if(!vis[i]) f[i] = mod + 1 - i, pri[++len] = i;
for(int j = 1; j <= len && i * pri[j] <= n; ++j){
vis[i * pri[j]] = 1;
if(i % pri[j] == 0){ f[i * pri[j]] = f[i]; break; }
f[i * pri[j]] = 1ll * f[i] * f[pri[j]] % mod;
}
}
for(int i = 1; i <= n; ++i) f[i] = 1ll * i * f[i] % mod, f[i] = (f[i] + f[i - 1]) % mod;
}
inline int calc(int n, int m){
return (1ll * n * (n + 1) / 2 % mod) * (1ll * m * (m + 1) / 2 % mod) % mod;
}
inline int sol(int n, int m){
int ans = 0;
for(int i = 1, j; i <= n; i = j + 1){
j = min(n / (n / i), m / (m / i));
ans = (ans + 1ll * (f[j] - f[i - 1] + mod) % mod * calc(n / i, m / i) % mod) % mod;
}
return ans;
}
int main(){
n = read(); m = read(); if(n > m) n ^= m ^= n ^= m;
seive(m); printf("%d", sol(n, m));
return 0;
}
```
六（[P2257](https://www.luogu.com.cn/problem/P2257) & [P2568](https://www.luogu.com.cn/problem/P2568)）. $T$ 组询问，每组询问给定 $n, m$，求
$$\sum_{k \in \mathbb{P}}\sum_{i=1}^n\sum_{j=1}^m [\gcd(i, j)=k]$$
其中 $\mathbb{P}$ 为质数集。
解：
还是推式子。
$$\begin{aligned}\text{原式}&=\sum_{k\in\mathbb{P}}\sum_{i=1}^{\left\lfloor \frac{n}{k} \right\rfloor}\sum_{j=1}^{\left\lfloor \frac{m}{k} \right\rfloor}[\gcd(i, j)=1]\\&=\sum_{k\in\mathbb{P}}\sum_{i=1}^{\left\lfloor \frac{n}{k} \right\rfloor}\sum_{j=1}^{\left\lfloor \frac{m}{k} \right\rfloor}\sum_{d\mid(i, j)}\mu(d)\\&=\sum_{k\in\mathbb{P}}\sum_{d=1}^{\left\lfloor \frac{n}{k} \right\rfloor}\mu(d)\left\lfloor \frac{n}{kd} \right\rfloor\left\lfloor \frac{m}{kd} \right\rfloor\end{aligned}$$
模仿上一道题的套路，记 $T=kd$，先枚举 $T$ 再枚举 $k$ 可得：
$$\text{原式}=\sum_{T=1}^n\sum_{k\in\mathbb{P}, k \mid T}\mu(\dfrac{T}{k})\left\lfloor \dfrac{n}{T} \right\rfloor\left\lfloor \dfrac{m}{T} \right\rfloor$$
预处理 $\sum_{k\in\mathbb{P}, k \mid T}\mu(\dfrac{T}{k})$ 的前缀和，然后直接数论分块，时间复杂度为 $O(\sum_{i=1}^N \dfrac{N}{i}+T\sqrt{N})$，即 $O(N\ln N + T\sqrt{N})$。
下面放一下 [P2257](https://www.luogu.com.cn/problem/P2257) 的代码：
```cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
inline int read(){
int x = 0, f = 1; char ch = getchar();
while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar(); }
while(ch >= '0' && ch <= '9'){ x = x * 10 + (ch ^ 48); ch = getchar(); }
return x * f;
}
const int N = 10000010;
int t, n, m, pri[N], mu[N], len;
long long s[N]; bool vis[N];
inline void seive(){
mu[1] = 1;
for(int i = 2; i <= N - 10; ++i){
if(!vis[i]) pri[++len] = i, mu[i] = -1;
for(int j = 1; j <= len && i * pri[j] <= N - 10; ++j){
vis[i * pri[j]] = 1;
if(i % pri[j] == 0){ mu[i * pri[j]] = 0; break; }
mu[i * pri[j]] = -mu[i];
}
}
for(int j = 1; j <= len; ++j){
for(int i = 1; i * pri[j] <= N - 10; ++i){
s[i * pri[j]] += (long long)mu[i];
}
}
for(int i = 1; i <= N - 10; ++i) s[i] += s[i - 1];
}
inline int sol(int n, int m){
if(n > m) n ^= m ^= n ^= m; long long ans = 0;
for(int i = 1, j; i <= n; i = j + 1){
j = min(n / (n / i), m / (m / i));
ans += 1ll * (s[j] - s[i - 1]) * (n / i) * (m / i);
}
return ans;
}
int main(){
t = read(); seive();
while(t--){
n = read(); m = read();
printf("%lld\n", sol(n, m));
}
return 0;
}
```
七（[P3768](https://www.luogu.com.cn/problem/P3768)）. 单组询问，每组询问给定 $n, p$，求
$$\sum_{i=1}^n\sum_{j=1}^nij\gcd(i,j)$$
解：
一顿操作猛如虎：
$$\begin{aligned}\text{原式}&=\sum_{d=1}^nd^3\sum_{i=1}^{\left\lfloor \frac{n}{d} \right\rfloor}\sum_{j=1}^{\left\lfloor \frac{n}{d} \right\rfloor}ij[\gcd(i, j)=1]\\&=\sum_{d=1}^nd^3\sum_{k=1}^{\left\lfloor \frac{n}{d} \right\rfloor}\mu(k)\cdot k^2\cdot S(\left\lfloor \frac{n}{kd} \right\rfloor, \left\lfloor \frac{n}{kd} \right\rfloor)\end{aligned}$$
其中 $S(n, m)=\sum_{i=1}^n\sum_{j=1}^mij=\dfrac{n(n+1)}{2}\cdot\dfrac{m(m+1)}{2}$
套路地令 $T=kd$，调换求和顺序可得：
$$\begin{aligned}\text{原式}&=\sum_{T=1}^nT^2\sum_{d\mid T}\mu(d)\cdot\dfrac{T}{d}\cdot S(\left\lfloor \frac{n}{T} \right\rfloor\left\lfloor \frac{n}{T} \right\rfloor)\\&=\sum_{T=1}^nT^2\cdot\varphi(T)\cdot S(\left\lfloor \frac{n}{T} \right\rfloor, \left\lfloor \frac{n}{T} \right\rfloor)\end{aligned}$$
用杜教筛求 $\varphi$ 的前缀和，然后数论分块就行，时间复杂度为 $O(n^{\frac{2}{3}})$。
```cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <tr1/unordered_map>
using namespace std;
using namespace std::tr1;
#define int long long
inline int read(){
int x = 0, f = 1; char ch = getchar();
while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar(); }
while(ch >= '0' && ch <= '9'){ x = x * 10 + (ch ^ 48); ch = getchar(); }
return x * f;
}
const int N = 5000010;
int inv2, inv6, mod, n, pri[N], len; bool vis[N];
int phi[N]; unordered_map <int, int> sphi;
inline int fpow(int n, int p){
n %= mod; int ans = 1, base = n;
while(p){
if(p & 1) ans = ans * base % mod;
base = base * base % mod;
p >>= 1;
}
return ans;
}
inline void seive(){
phi[1] = 1;
for(int i = 2; i <= N - 10; ++i){
if(!vis[i]) pri[++len] = i, phi[i] = i - 1;
for(int j = 1; j <= len && i * pri[j] <= N - 10; ++j){
vis[i * pri[j]] = 1;
if(i % pri[j] == 0){ phi[i * pri[j]] = phi[i] * pri[j] % mod; break; }
phi[i * pri[j]] = phi[i] * phi[pri[j]] % mod;
}
}
for(int i = 1; i <= N - 10; ++i) phi[i] = (phi[i - 1] + phi[i] * i % mod * i % mod) % mod;
}
inline int sum1(int n){ return n * (n + 1) % mod * inv2 % mod; }
inline int sum2(int n){ return n * (n + 1) % mod * ((2 * n + 1) % mod) % mod * inv6 % mod; }
inline int sum3(int n){ return sum1(n) * sum1(n) % mod; }
inline int getphi(int n){
if(n <= N - 10) return phi[n];
if(sphi[n]) return sphi[n];
int ans = sum3(n % mod);
for(int i = 2, j; i <= n; i = j + 1){
j = n / (n / i);
ans = (ans - (sum2(j % mod) - sum2((i - 1) % mod) + mod) % mod * getphi(n / i) % mod + mod) % mod;
}
return sphi[n] = ans;
}
inline int sol(int n){
int ans = 0;
for(int i = 1, j; i <= n; i = j + 1){
j = n / (n / i);
ans = (ans + (getphi(j) - getphi(i - 1) + mod) % mod * sum3((n / i) % mod) % mod) % mod;
}
return ans;
}
signed main(){
mod = read(); n = read(); seive();
inv2 = fpow(2, mod - 2); inv6 = fpow(6, mod - 2);
printf("%lld\n", sol(n));
return 0;
}
```
还有好几道例题就先咕着吧，毕竟还有学校作业没写（
哦对了如果有错请指出并 D 死这个彩笔（