学习笔记 ---- 莫比乌斯反演总结

概述

对于一些函数 $f(n)$，如果很难直接求出它的值，但是容易求出其约数或倍数的$g(n)$和，并且$f$与$g$ 满足一定关系。那么可以通过莫比乌斯反演求出 $f(n)$。

前置知识

数论分块

点这里

狄利克雷卷积

还不会，先鸽着

积性函数

设 $T$ 为函数 $f$ 的定义域。如果 $\forall a,b\in T且gcd(a,b)=1$ 都有 $f(ab)=f(a)\times f(b)$，那么称函数 $f$ 为积性函数。

一个很好的性质是几乎所有积性函数都能用 线性筛 筛出来。

常见的积性函数有欧拉函数和莫比乌斯函数

莫比乌斯函数

定义

$\mu (n)$ 为莫比乌斯函数，定义为：

$\mu (n)=\{\begin{array}{ll}1& n=1\\ 0& n含有平方因子\\ (-1{)}^k& k为n本质不同的质因子数\end{array}$

性质

1. 莫比乌斯函数是积性函数
2. ${\sum }_{d|n}\mu (d)=[n=1]$

第二条性质非常重要，可以将一个逻辑表达式的值转化为对 $\mu$ 函数求和。下面证明一下：

1. 当 $n=1$ 时： ${\sum }_{d|n}\mu (d)=\mu (1)=1$，显然等于右边。

2. 当 $n\ne 1$ 时：我们考虑写出 $n$ 质因数分解后的形式 $n=p_1^{c_1}\times p_2^{c_2}\times ...\times p_k^{c_k}$。然后如果一个因子 $d$ 含有某个 $p_1\sim p_k$ 的幂次大于 $1$，那么根据莫比乌斯函数的定义，此时 $\mu (d)=0$。因此我们只需要考虑每个质因数是否出现在 $d$ 中 即可。

   那么有 ${\sum }_{d|n}\mu (d)={\sum }_{i=0}^k\left(\genfrac{}{}{0ex}{}{k}{i}\right)(-1{)}^i=(1-1{)}^k=0$

综上，得证。

补充结论：$[gcd(i,j)=1]={\sum }_{d|gcd(i,j)}\mu (d)$

这个由上述性质可以直接得到。

求莫比乌斯函数模版：

int mu[N], prime[N], tot;
bool vis[N];
void pre() {
	mu[1] = 1; // 注意1是特殊的
	for(int i = 2; i < N; i ++ ) {
		if(!vis[i]) {prime[++ tot] = i; mu[i] = -1;} // 根据定义，质数的莫比乌斯函数为-1 
		for(int j = 1; i * prime[j] < N && j <= tot; j ++ ) {
			vis[i * prime[j]] = 1;
			if(i % prime[j] == 0) {
				mu[i * prime[j]] = 0; // 含有平方因子，莫比乌斯函数为0 
				break;
			}
			mu[i * prime[j]] = -mu[i]; // 根据积性函数的性质， mu[i * prime[j]] = mu[i] * mu[prime[j]] = -mu[i] 
		}
	} 
}

莫比乌斯反演

因子形式

若 $F(n)={\sum }_{d|n}f(d)$，则 $f(n)={\sum }_{d|n}\mu (\frac{n}{d})F(d)$。

证明：
将 $F(d)$ 带入，那么有：
${\sum }_{d|n}\mu (\frac{n}{d})F(d)$
$={\sum }_{d|n}\mu (\frac{n}{d}){\sum }_{k|d}f(k)$
$={\sum }_{k|n}f(k){\sum }_{t|\frac{n}{k}}\mu (t)$

根据莫比乌斯函数的性质 $2$：当 $\frac{n}{k}=1$ 时，右边的和式为 $1$，此时 $n=k$，那么贡献为 $f(n)。$ 否则右边的和式为 $0$，$k$ 没有贡献。

因此结果为 $右边=f(n)=左边$。

倍数形式

若 $F(n)={\sum }_{n|d}f(d)$，则 $f(n)={\sum }_{n|d}\mu (\frac{d}{n})F(d)$

证明：
将 $F(d)$ 带入，那么有：
${\sum }_{n|d}\mu (\frac{d}{n})F(d)$
$={\sum }_{n|d}\mu (\frac{d}{n}){\sum }_{d|k}f(k)$
$={\sum }_{n|k}f(k){\sum }_{t|\frac{k}{n}}\mu (t)$

只有当$\frac{k}{n}=1$ 时，$f(k)$ 有贡献。此时 $k=n$，只有一个 $f(n)$ 算入到了答案中。

因此 $右边=f(n)=左边$。

实际上，上述两个形式并不太常用。通常情况下只用到 $[gcd(i,j)=1]={\sum }_{d|gcd(i,j)}\mu (d)$ 这一个性质就足够了。但是回归本质：如果我们发现 $F$ 函数好求，而 $f$ 函数不好求，并且 $F$ 与 $f$ 函数满足上述两种关系之一。那么我们可以通过求出 $F$ 来反演得到 $f$。

例题

周期性字符串

点这里
题意：
如果一个字符串 $s$ 可以由另一个字符串 $t(t\ne s)$ 重复若干次得到，那么称 $s$ 具有周期性。给定一个 $n$，求有多少长度为 $n$ 的周期字符串。 $1\le n\le 10^6$

分析：

首先可以 $dp$。设 $f_i$ 表示长度为 $i$ 的周期性字符串个数。那么有转移 $f_i=\sum _{j|i}26^j-f_j$。预处理 $26$ 的幂次复杂度可做到 $O(n\ln n)$。能够通过本题，但是如果 $n$ 开到 $10^7$ 就容易寄。

我们考虑莫比乌斯反演。设 $g_i$ 表示长度为 $i$ 且非周期性字符串个数，设 $h_i$ 表示所有长度为 $i$ 的因数的非周期性字符串个数。那么显然 $h_n={\sum }_{d|n}g(d)$，答案就是 ${\sum }_{d|n,d\ne n}g(d)$。

我们发现 $h_i=26^i$。这是因为任意一个长度为 $i$ 的字符串 $s$ 都可以对应一个最小的长度是 $i$ 因数的非周期字符串 $t$。任意一个长度为 $i$ 因数非周期性字符串 $t$ 也都可以通过复制拼接唯一对应一个长度为 $i$ 的字符串 $s$。因此这建立了一个双射，所以二者是相等的。

然后我们只需要把所以 $d|n,d\ne n$ 的 $g(d)$ 用 $h$ 反演出来即可。时间复杂度 $O(\sqrt{n}\times \sqrt{n}=n)$

CODE：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
typedef long long LL;
const LL mod = 1e9 + 7;
int n, mu[N], prime[N], tot;
bool vis[N];
LL f[N], F[N], res;
inline LL Pow(LL x, LL y) {
	LL res = 1LL, k = x;
	while(y) {
		if(y & 1) res = (res * k) % mod;
		y >>= 1;
		k = (k * k) % mod;
	}
	return res;
}
void Get_mu() {
	mu[1] = 1;
	for(int i = 2; i < N; i ++ ) {
		if(!vis[i]) {prime[++ tot] = i; mu[i] = -1;}
		for(int j = 1; j <= tot && i * prime[j] < N; j ++ ) {
			vis[i * prime[j]] = 1;
			if(i % prime[j] == 0) {
				mu[i * prime[j]] = 0;
				break;
			}
			mu[i * prime[j]] = -mu[i];
  		}
	}
}
void calc(int n) {
	for(int d = 1; d * d <= n; d ++ ) {
		if(n % d == 0) {
			F[n] = ((F[n] + 1LL * mu[d] * f[n / d] % mod) % mod + mod) % mod;
			if(d * d != n) F[n] = ((F[n] + 1LL * mu[n / d] * f[d] % mod) % mod + mod) % mod;
		}
	}
}
int main() {
	Get_mu();
	cin >> n;
	for(int i = 1; i * i <= n; i ++ ) {
		if(n % i == 0) {
			f[i] = Pow(26LL, 1LL * i);
			f[n / i] = Pow(26LL, 1LL * (n / i));
		}
	}
	for(int i = 1; i * i <= n; i ++ ) {
		if(n % i == 0 && i != n) {
			calc(i); res = (res + F[i]) % mod;
			if(i * i != n && n / i != n) calc(n / i), res = (res + F[n / i]) % mod;
		}
	}
	cout << res << endl;
	return 0;
}

互质数对

点这里
题意：
给定一个 $n$，求 ${\sum }_{i=1}^n{\sum }_{j=1}^n[gcd(i,j)=1]$。$n\le 10^7$

分析：
看到 $[gcd(i,j)=1]$，想到莫比乌斯函数。
${\sum }_{i=1}^n{\sum }_{j=1}^n[gcd(i,j)=1]$
$={\sum }_{i=1}^n{\sum }_{j=1}^n\sum _{d|gcd(i,j)}\mu (d)$

把枚举质因数提前

$={\sum }_{d=1}^n\mu (d)\times \lfloor \frac{n}{d}\rfloor \times \lfloor \frac{n}{d}\rfloor$

处理出 $u(i)$ 的前缀和，然后一维数论分块就行。
复杂度 $O(\sqrt{n})$

CODE：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e7 + 10;
int n, prime[N], tot;
bool vis[N];
LL mu[N], sum[N], res;
void Get_mu() {
	mu[1] = 1;
	for(int i = 2; i < N; i ++ ) {
		if(!vis[i]) {prime[++ tot] = i; mu[i] = -1;}
		for(int j = 1; j <= tot && 1LL * i * prime[j] < 1LL * N; j ++ ) {
			vis[i * prime[j]] = 1;
			if(i % prime[j] == 0) {
				mu[i * prime[j]] = 0;
				break;
			}
			mu[i * prime[j]] = -mu[i];
		}
	}
	for(int i = 1; i < N; i ++ ) sum[i] = sum[i - 1] + mu[i];
}
int main() {
	Get_mu();
	cin >> n;
	int l = 1, r;
	while(l <= n) {
		r = n / (n / l);
		res = res + (sum[r] - sum[l - 1]) * (1LL * n / l) * (1LL * n / l);
		l = r + 1;
	}
	cout << res << endl;
	return 0;
}

[NOI2010D1T1]能量采集

点这里
题意：给你 $n,m$，求 ${\sum }_{i=1}^n{\sum }_{j=1}^{m}2\times gcd(i,j)-1$。 $1\le n,m\le 10^5$。

分析：
看到 $gcd(i,j)$，可以考虑莫比乌斯函数。
枚举 $gcd$：
${\sum }_{i=1}^n{\sum }_{j=1}^{m}2\times gcd(i,j)-1$
$={\sum }_{i=1}^n{\sum }_{j=1}^m{\sum }_{d=1}^{min(n,m)}(2\times d-1)\times ([gcd(i,j)=d])$

提前枚举 $gcd$

$={\sum }_{d=1}^{min(n,m)}(2\times d-1)\times {\sum }_{i=1}^n{\sum }_{j=1}^m[gcd(i,j)=d]$

右边的两个求和符号上指标同时除以 $d$，变为枚举 $d$ 的倍数：

$={\sum }_{d=1}^{min(n,m)}(2\times d-1)\times {\sum }_{i=1}^{\lfloor \frac{n}{d}\rfloor }{\sum }_{j=1}^{\lfloor \frac{m}{d}\rfloor }[gcd(i,j)=1]$

$={\sum }_{d=1}^{min(n,m)}(2\times d-1){\sum }_{i=1}^{\lfloor \frac{n}{d}\rfloor }{\sum }_{j=1}^{\lfloor \frac{m}{d}\rfloor }{\sum }_{k|gcd(i,j)}\mu (k)$
$={\sum }_{d=1}^{min(n,m)}(2\times d-1){\sum }_{k=1}^{min(\lfloor \frac{n}{d}\rfloor ,\lfloor \frac{m}{d}\rfloor )}\mu (k)\times \lfloor \frac{n}{dk}\rfloor \times \lfloor \frac{m}{dk}\rfloor$

然后考虑对于 $d$ 而言， $\lfloor \frac{n}{d}\rfloor$ 和 $\lfloor \frac{m}{d}\rfloor$ 成块状分布，可以二维分块得到 $n^{\prime }=\lfloor \frac{n}{d}\rfloor$ 和 $m^{\prime }=\lfloor \frac{m}{d}\rfloor$。对于 $n^{\prime }$ 和 $m^{\prime }$ 分别相同的的一段内，右边和式的贡献是相同的，变成了 ${\sum }_{k=1}^{min(n^{\prime },m^{\prime })}\mu (k)\times \lfloor \frac{n^{\prime }}{k}\rfloor \times \lfloor \frac{m^{\prime }}{k}\rfloor$。也可以再二维整除分块一次，总复杂度就是 $O(\sqrt{n}\times \sqrt{n}=n)$ 的。

实际上复杂度还能做到 $O(\sqrt{n})$，这个后边会讲。

CODE：

// 整除套整除分块 好像能做到 O(n) 
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
typedef long long LL;
int n, m, prime[N], tot;
LL mu[N], sum[N], res;
bool vis[N];
void Get_mu() {
	mu[1] = 1;
	for(int i = 2; i < N; i ++ ) {
		if(!vis[i]) {prime[++ tot] = i; mu[i] = -1;}
		for(int j = 1; j <= tot && i * prime[j] < N; j ++ ) {
			vis[i * prime[j]] = 1;
			if(i % prime[j] == 0) {
				mu[i * prime[j]] = 0;
				break;
			}
			mu[i * prime[j]] = -mu[i]; // 积性函数性质 
		}
	}
	for(int i = 1; i < N; i ++ ) sum[i] = sum[i - 1] + mu[i];
} 
LL calc(int nt, int mt) {
	int t = min(nt, mt);
	int l = 1, r; LL res = 0;
	while(l <= t) {
		r = min({t, nt / (nt / l), mt / (mt / l)});
		res = res + 1LL * (nt / l) * (mt / l) * (sum[r] - sum[l - 1]);
		l = r + 1;
	}
	return res;
}
int main() {
	scanf("%d%d", &n, &m);
	Get_mu();
	int t = min(n, m);
	int l = 1, r;
	while(l <= t) {
		r = min({t, n / (n / l), m / (m / l)});
		res = res + calc(n / l, m / l) * (1LL * (l + r) * (r - l + 1) - 1LL * (r - l + 1));
		l = r + 1;
	}
	printf("%lld\n", res);
	return 0;
}

BZOJ2820 YY的GCD

点这里
题意：
$T$ 次询问，每次给你 $n,m$，问${\sum }_{i=1}^n{\sum }_{j=1}^m[gcd(i,j)=p],p代表质数$。
$T\le 10^4,1\le n,m\le 10^7$

分析：
首先看到 逻辑表达式的值 和 $gcd(i,j)$，考虑莫反。
如果我们定义 $f(x)=\{\begin{array}{ll}1& x\in P\\ 0& x\notin P\end{array}$，$P$ 代表素数集合。那么所要求的就是：
${\sum }_{i=1}^n{\sum }_{j=1}^{m}f(gcd(i,j))$
$={\sum }_{d=1}^{min(n,m)}f(d){\sum }_{i=1}^n{\sum }_{j=1}^m[gcd(i,j)=d]$
$={\sum }_{d=1}^{min(n,m)}f(d){\sum }_{i=1}^{\lfloor \frac{n}{d}\rfloor }{\sum }_{j=1}^{\lfloor \frac{m}{d}\rfloor }[gcd(i,j)=1]$
$={\sum }_{d=1}^{min(n,m)}f(d){\sum }_{i=1}^{\lfloor \frac{n}{d}\rfloor }{\sum }_{j=1}^{\lfloor \frac{m}{d}\rfloor }{\sum }_{k|gcd(i,j)}\mu (k)$
$={\sum }_{d=1}^{min(n,m)}f(d){\sum }_{k=1}^{min(\lfloor \frac{n}{d}\rfloor ,\lfloor \frac{m}{d}\rfloor )}\mu (k)\times \lfloor \frac{n}{dk}\rfloor \times \lfloor \frac{m}{dk}\rfloor$

首先 $f$ 数组的求解是简单的，可以在 $O(N)$ 的复杂度内预处理出来。然后我们可以使用上一题的思路，二次分块，但是那样每次询问复杂度是 $O(n)$ 的，总复杂度就变成 $O(Tn)$，无法接受。

怎么办呢？我们好像已经化到了最简，无法进一步优化了。

这里有一个很通用的技巧，也算一个很重要的套路：

当我们需要二次分块时，一般第二个求和符号后面的分母都是两个变量的乘积。尝试把乘积提前枚举，并将式子变形。往往能得到一个可以预处理的函数，使得复杂度少一个 $\sqrt{n}$。

我们来尝试一下：

首先理解一下式子的含义：相当于把所有满足 $dk\le min(n,m)$ 的数对 $(d,k)$ 都贡献一个 $f(d)\times \mu (k)\times \lfloor \frac{n}{dk}\rfloor \lfloor \frac{m}{dk}\rfloor$ 到答案中。

设 $dk=T$，那么有：
${\sum }_{d=1}^{min(n,m)}f(d){\sum }_{k=1}^{min(\lfloor \frac{n}{d}\rfloor ,\lfloor \frac{m}{d}\rfloor )}\mu (k)\times \lfloor \frac{n}{dk}\rfloor \times \lfloor \frac{m}{dk}\rfloor$
$={\sum }_{T=1}^{min(n,m)}\lfloor \frac{n}{T}\rfloor \times \lfloor \frac{m}{T}\rfloor {\sum }_{d|T}f(d)\times \mu (\frac{T}{d})$。

设 $F(T)={\sum }_{d|T}f(d)\times \mu (\frac{T}{d})$。那么原式变成了

${\sum }_{T=1}^{min(n,m)}\lfloor \frac{n}{T}\rfloor \times \lfloor \frac{m}{T}\rfloor \times F(T)$。

我们发现 $F(T)$ 是可以在 $O(N\ln N)$ 的复杂度内预处理出来的，因此每次询问只需要一次二维数论块就可以了。

为什么这样做复杂度就能够优化呢？
我们考虑变形前的式子中 两个求和符号都是与每次给定的 $n$ 与 $m$ 相关的，这样就无法预处理。而如果我们让第一个求和符号枚举乘积，第二个求和符号枚举因子，那么第二个求和就只与乘积$T$的大小有关，与 $n,m$ 无关了。因此一般可以预处理。

实际上本题的预处理可以做到线性。一些较难的题目也会在预处理上做文章，需要线性的做法才能通过。而 $F$ 数组大多都是两个函数的 卷积，可以根据卷积的一些性质来求。

总复杂度就是 $O(N\ln N+T\sqrt{n})$，其中 $N$ 是 $n$ 的上限。

CODE：

// 好像会线性了？ 
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e7 + 10;
LL f[N], sum[N];
int T, n, m, mu[N];
int prime[N], tot;
bool vis[N];
void Get_mu() {
	mu[1] = 1;
	for(int i = 2; i < N; i ++ ) {
		if(!vis[i]) {prime[++ tot] = i; mu[i] = -1; f[i] = 1LL;}
		for(int j = 1; j <= tot && 1LL * i * prime[j] < 1LL * N; j ++ ) {
			vis[i * prime[j]] = 1;
			if(i % prime[j] == 0) {
				mu[i * prime[j]] = 0;
				f[i * prime[j]] = mu[i];
				break;
			}
			mu[i * prime[j]] = -mu[i];
			f[i * prime[j]] = -f[i] + mu[i];
		}
	}
	for(int i = 1; i < N; i ++ ) sum[i] = sum[i - 1] + f[i];
}
LL calc(int n, int m) {
	int l = 1, r; LL res = 0;
	int t = min(n, m);
	while(l <= t) {
		r = min({t, n / (n / l), m / (m / l)});
		res = res + 1LL * (n / l) * (m / l) * (sum[r] - sum[l - 1]);
		l = r + 1;
	}
	return res;
}
int main() {
	Get_mu();
	scanf("%d", &T);
	while(T -- ) {
		scanf("%d%d", &n, &m);
		printf("%lld\n", calc(n, m));
	}
	return 0;
}

[SDOI2015] 约数个数和

点这里
题意：设 $d(x)$ 为 $x$ 的因数个数。$T$ 次询问，每次给定 $n,m$，求 ${\sum }_{i=1}^n{\sum }_{j=1}^{m}d(i\times j)$ 。
$T\le 5\times 10^4，1\le n,m\le 5\times 10^4$

首先有一个对本题而言非常重要的结论：
$d(x\times y)={\sum }_{i|x}{\sum }_{j|y}[gcd(i,j)=1]$

证明一下：
设 $P(n)$ 表示 $n$ 质因数分解后的质因子集合。
那么设 P ( x × y ) = { p 1 , p 2 , . . . , p k } P(x \times y) = \left \{ p_1,p_2,...,p_k\right \} P(x×y)={p1​,p2​,...,pk​}

设 $x=p_1^{c_1}{p}_2^{c_2}...p_k^{c_k}$
设 $y=p_1^{t_1}{p}_2^{t_2}...p_k^{t_k}$

那么很显然 $x\times y$ 的因子数量为 ${\prod }_{i=1}^k(c_i+t_i+1)$
然后考虑 ${\sum }_{i|x}{\sum }_{j|y}[gcd(i,j)=1]$ 什么时候会对答案有贡献。
需要对于 $p_1\sim p_k$ 这 $k$ 个质因数，$x$ 不含 或者 $y$ 不含。

对于一个素数$p_i$

1. $x$ 不含，$y$ 含。这种情况有 $t_i$ 种
2. $x$ 含， $y$ 不含。这种情况有 $c_i$ 种
3. $x$ 不含，且 $y$ 不含。这种情况有 $1$ 种。

因此每一个 $i$ 的方案数都是都是 $c_i+t_i+1$ 种。由于是分步。需要把它们乘起来，总方案数就是 ${\prod }_{i=1}^k(c_i+t_i+1)$。每一种方案都唯一对应了一个数对 $(p,q)$，满足 $p|x,q|y$ 且 $gcd(p,q)=1$。

那么原问题就变成求 ${\sum }_{i=1}^n{\sum }_{j=1}^m{\sum }_{p|i}{\sum }_{q|j}[gcd(p,q)=1]$
$={\sum }_{i=1}^n{\sum }_{j=1}^m{\sum }_{p|i}{\sum }_{q|j}{\sum }_{k|gcd(p,q)}\mu (k)$

变成先枚举 $k$，再枚举 $p,q$，最后枚举 $i,j$ 的形式

$={\sum }_{k=1}^{min(n,m)}\mu (k){\sum }_{p=1}^{\lfloor \frac{n}{k}\rfloor }{\sum }_{q=1}^{\lfloor \frac{m}{k}\rfloor }\lfloor \frac{n}{kp}\rfloor \times \lfloor \frac{m}{kq}\rfloor$

$={\sum }_{k=1}^{min(n,m)}\mu (k)\times {\sum }_{p=1}^{\lfloor \frac{n}{k}\rfloor }\lfloor \frac{n}{kp}\rfloor \times {\sum }_{q=1}^{\lfloor \frac{m}{k}\rfloor }\lfloor \frac{m}{kq}\rfloor$

记 $f(n)={\sum }_{i=1}^n\lfloor \frac{n}{i}\rfloor$

那么原式就是

$={\sum }_{k=1}^{min(n,m)}\mu (k)\times f(\lfloor \frac{n}{k}\rfloor )\times f(\lfloor \frac{m}{k}\rfloor )$

然后数论分块预处理 $f$，每次询问一维数论分块求出答案即可。
时间复杂度 $O(n\sqrt{n}+T\sqrt{n})$

CODE：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 5e4 + 10;
int T, n, m;
int mu[N], prime[N], tot, sum[N];
LL S[N];
bool vis[N];
void get_mu() {
	mu[1] = 1;
	for(int i = 2; i < N; i ++ ) {
		if(!vis[i]) {prime[++ tot] = i, mu[i] = -1;}
		for(int j = 1; j <= tot && i * prime[j] < N; j ++ ) {
			vis[i * prime[j]] = 1;
			if(i % prime[j] == 0) {
				mu[i * prime[j]] = 0;
				break;
			}
			mu[i * prime[j]] = -mu[i];
		}
	}
	for(int i = 1; i < N; i ++ ) sum[i] = sum[i - 1] + mu[i];
}
void getS(int n) {
	int l = 1, r; 
	while(l <= n) {
		r = n / (n / l);
		S[n] = (S[n] + 1LL * (r - l + 1) * (n / l));
		l = r + 1;
	}
}
inline LL calc(int n, int m) {
	int t = min(n, m);
	int l = 1, r; LL res = 0;
	while(l <= t) {
		r = min({t, n / (n / l), m / (m / l)});
		res = res + S[n / l] * S[m / l] * 1LL * (sum[r] - sum[l - 1]);
		l = r + 1;
	}
	return res;
}
int main() {
	get_mu();
	for(int i = 1; i < N; i ++ ) getS(i);
	scanf("%d", &T);
	while(T -- ) {
		scanf("%d%d", &n, &m);
		printf("%lld\n", calc(n, m));
	}
	return 0;
}

BZOJ4407 于神之怒加强版

点这里
题意：
给你 $T,k$，$T$次询问，每次询问给定 $n,m$，求 ${\sum }_{i=1}^n{\sum }_{j=1}^{m}gcd(i,j{)}^{k}mod10^9+7$
$1\le T\le 2\times 10^3$，$1\le n,m\le 5\times 10^6$

分析：
看到 $gcd$，还是想到枚举 $gcd$，然后乘一个逻辑表达式。

${\sum }_{i=1}^n{\sum }_{j=1}^{m}gcd(i,j{)}^{k}mod10^9+7$
$={\sum }_{d=1}^{min(n,m)}{d}^k{\sum }_{i=1}^n{\sum }_{j=1}^m[gcd(i,j)=d]$

右边的两个求和老演员了。

$={\sum }_{d=1}^{min(n,m)}{d}^k{\sum }_{i=1}^{\lfloor \frac{n}{d}\rfloor }{\sum }_{j=1}^{\lfloor \frac{m}{d}\rfloor }[gcd(i,j)=1]$
$={\sum }_{d=1}^{min(n,m)}{d}^k{\sum }_{t=1}^{min(\lfloor \frac{n}{d}\rfloor ,\lfloor \frac{m}{d}\rfloor )}\mu (t)\times \lfloor \frac{n}{dt}\rfloor \times \lfloor \frac{m}{dt}\rfloor$

$={\sum }_{T=1}^{min(n,m)}\lfloor \frac{n}{T}\rfloor \times \lfloor \frac{m}{T}\rfloor {\sum }_{d|T}{d}^k\times \mu (\frac{T}{d})$

设 $F(T)={\sum }_{d|T}{d}^k\times \mu (\frac{T}{d})$

$={\sum }_{T=1}^{min(n,m)}\lfloor \frac{n}{T}\rfloor \times \lfloor \frac{m}{T}\rfloor \times F(T)$

求出 $F(T)$ 的前缀和每次询问一维数论分块就可以了。
时间复杂度 $O(n\log n+T\sqrt{n})$

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 5e6 + 10;
const LL mod = 1e9 + 7;
int T, n, m, tot;
bool vis[N];
LL k, mu[N], prime[N], f[N], val[N];
LL sum[N];
inline LL Pow(LL x, LL y) {
	LL res = 1LL, k = x;
	while(y) {
		if(y & 1) res = (res * k) % mod;
		y >>= 1;
		k = (k * k) % mod;
	}
	return res;
}
void pre() {
	for(int i = 1; i < N; i ++ ) val[i] = Pow(1LL * i, k);
	mu[1] = 1;
	for(int i = 2; i < N; i ++ ) {
		if(!vis[i]) {prime[++ tot] = i; mu[i] = -1;}
        for(int j = 1; i * prime[j] < N && j <= tot; j ++ ) {
        	vis[i * prime[j]] = 1;
        	if(i % prime[j] == 0) {
        		mu[i * prime[j]] = 0;
        		break;
			}
			mu[i * prime[j]] = -mu[i];
		}
	}
	for(int i = 1; i < N; i ++ ) {
		for(int j = 1; j * i < N; j ++ ) {
			f[i * j] = (f[i * j] + mu[i] * val[j] % mod) % mod;
		}
	}
	for(int i = 1; i < N; i ++ ) sum[i] = (sum[i - 1] + f[i]) % mod;
}
LL calc(int n, int m) {
	LL res = 0;
	int l = 1, r, t = min(n, m);
	while(l <= t) {
		r = min({n / (n / l), m / (m / l), t});
		res = (res + ((sum[r] - sum[l - 1]) % mod + mod) % mod * 1LL * (n / l) % mod * (m / l) % mod) % mod;
		l = r + 1;
	}
	return res;
}
int main() {
	scanf("%d%lld", &T, &k);
	pre();
	while(T -- ) {
		scanf("%d%d", &n, &m);
		printf("%lld\n", calc(n, m));
	}
	return 0;
}

【BZOJ2693】jzptab最小公倍数之和

题意：
给你一个 $T$， $T$组询问，每次给定一个 $n,m$。求${\sum }_{i=1}^n{\sum }_{j=1}^{m}lcm(i,j)$。答案对 $10^8+9$ 取模。
$1\le T\le 10^4$，$1\le n,m\le 10^7$

分析：
我们都知道 $lcm(i,j)=\frac{i\times j}{gcd(i,j)}$
所以有
${\sum }_{i=1}^n{\sum }_{j=1}^{m}lcm(i,j)$
$={\sum }_{i=1}^n{\sum }_{j=1}^m\frac{i\times j}{gcd(i,j)}$
$={\sum }_{d=1}^{min(n,m)}\frac{1}{d}{\sum }_{i=1}^n{\sum }_{j=1}^{m}i\times j\times [gcd(i,j)=d]$
$={\sum }_{d=1}^{min(n,m)}\frac{1}{d}{\sum }_{i=1}^{\lfloor \frac{n}{d}\rfloor }{\sum }_{j=1}^{\lfloor \frac{m}{d}\rfloor }(id)\times (jd)\times [gcd(i,j)=1]$
$={\sum }_{d=1}^{min(n,m)}d{\sum }_{i=1}^{\lfloor \frac{n}{d}\rfloor }{\sum }_{j=1}^{\lfloor \frac{m}{d}\rfloor }i\times j\times {\sum }_{k|gcd(i,j)}\mu (k)$
$={\sum }_{d=1}^{min(n,m)}d{\sum }_{k=1}^{min(\lfloor \frac{n}{d}\rfloor ,\lfloor \frac{m}{d}\rfloor )}\mu (k){\sum }_{i=1}^{\lfloor \frac{n}{dk}\rfloor }{\sum }_{j=1}^{\lfloor \frac{m}{dk}\rfloor }(ik)\times (jk)$
$={\sum }_{d=1}^{min(n,m)}d{\sum }_{k=1}^{min(\lfloor \frac{n}{d}\rfloor ,\lfloor \frac{m}{d}\rfloor )}\mu (k)\times k^2\times f(\lfloor \frac{n}{dk}\rfloor )\times f(\lfloor \frac{m}{dk}\rfloor )$

其中 $f(n)={\sum }_{i=1}^{n}i=\frac{n\times (n+1)}{2}$

然后设 $T=dk$

$={\sum }_{T=1}^{min(n,m)}f(\lfloor \frac{n}{T}\rfloor )\times f(\lfloor \frac{m}{T}\rfloor ){\sum }_{d|T}{d}^2\times (\frac{T}{d})\times \mu (d)$
$={\sum }_{T=1}^{min(n,m)}f(\lfloor \frac{n}{T}\rfloor )\times f(\lfloor \frac{m}{T}\rfloor ){\sum }_{d|T}d\times T\times \mu (d)$

设 $F(T)=T\times {\sum }_{d|T}d\times \mu (d)$
$F(T)$ 可以在$O(n\ln n)$ 的复杂度内预处理，但这样还是会超时。

其实我们可以对于每个 $T$，求出 $F(T)={\sum }_{d|T}d\times \mu (d)$，然后再乘 $T$ 就可以了。
接着发现 $F$ 是积性函数，因为对于互质的 $n,m$， $F(nm)=F(n)\times F(m)$。这是因为 $n,m$ 互质，所以任意一个 $nm$ 的因数$t$ 都能表示成$n$ 的一个因数 $p$ 乘 $m$ 的一个因数 $q$的形式。而由于莫比乌斯函数是积性函数，因此 $t\times \mu (t)=p\times q\times \mu (p)\times \mu (q)$。证明了 $F$ 是积性函数。

我们考虑在线性筛的过程中求出 $F$ 函数：
对于当前 $i$ 和素数 $p$

1. $i\%p\ne 0$，那么 $F[i\times p]=F[i]\times F[p]$。因为 $i,p$ 互质
2. $i\%p=0$，那么$F[i\times p]=F[i]$。分枚举因数 $d$ 时包不包括新加进来的 $p$ 两种情况考虑：如果不包括，那就是 $F[i]$。如果包括，那么此时 $d$ 中 $p$ 的幂次一定大于 $1$， $\mu (d)=0$，没有贡献。
3. 对于质数 $p$，$F[p]=1-p$

这样就能线性求出 $F$ 了。然后每次询问一维数论分块就好了。
复杂度 $O(n+T\sqrt{n})$

CODE：

// 两次分块可以把复杂度做到O(n)，但是如果多测就寄了
// 一般套路是考虑把第二次分块里的分母(不换元)提出来枚举，然后里面的函数观察发现是积性函数可以提前预处理 
// 然后就可以变成一次分块了。时间复杂度O(T√n) 
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod = 1e8 + 9;
const int N = 1e7 + 10;
int T, n, m, mu[N], prime[N], tot;
bool vis[N];
LL F[N];
void pre() {
	mu[1] = 1; F[1] = 1;
	for(int i = 2; i < N; i ++ ) {
		if(!vis[i]) {prime[++ tot] = i; mu[i] = -1; F[i] = (mod + 1LL - i);}
		for(int j = 1; 1LL * i * prime[j] < 1LL * N && j <= tot; j ++ ) {
			vis[i * prime[j]] = 1;
			if(i % prime[j] == 0) {
				mu[i * prime[j]] = 0;
				F[i * prime[j]] = F[i];
				break;
			}
			mu[i * prime[j]] = -mu[i];
			F[i * prime[j]] = F[i] * F[prime[j]] % mod;
		}
	}
	for(int i = 1; i < N; i ++ ) {
		F[i] = F[i] * 1LL * i % mod;
		F[i] = (F[i] + F[i - 1]) % mod;
	}
}
inline LL f(int n) {
	return 1LL * (n + 1LL) * n / 2 % mod;
}
LL calc(int n, int m) {
	int t = min(n, m);
	int l = 1, r; LL res = 0;
	while(l <= t) {
		r = min({n / (n / l), m / (m / l), t});
		res = ((res + f(n / l) * f(m / l) % mod * (F[r] - F[l - 1]) % mod) % mod + mod) % mod;
		l = r + 1;
	}
	return res;
}
int main() {
	pre();
	scanf("%d", &T);
	while(T -- ) {
		scanf("%d%d", &n, &m);
		printf("%lld\n", calc(n, m));
	}
	return 0;
}

[bzoj3529-Sdoi2014] 数表

点这里
题意：
设 $f(n)={\sum }_{d|n}d$。 $Q$ 次询问，每次给你 $n,m,a$，求 ${\sum }_{i=1}^n{\sum }_{j=1}^{m}f(gcd(i,j))[f(gcd(i,j))\le a]$
$1\le n,m\le 10^5$， $1\le Q\le 2\times 10^4$

分析：
$[f(gcd(i,j))\le a]$ 的限制不好做。
我们考虑设一个新函数 $g(n)=\{\begin{array}{ll}f(n)& f(n)\le a\\ 0& f(n)>a\end{array}$
那么式子变成了 ${\sum }_{i=1}^n{\sum }_{j=1}^{m}g(gcd(i,j))$
由于 $gcd$ 的取值比较小，我们可以求出所有的 $f(n)$。然后按照 $f(n)$ 从小到大的顺序把 $n$ 排序，把询问按照 $a$ 从小到大的顺序排序后，我们就可以每次加入一些 $n$，把他们的 $g(n)$ 由 $0$ 变为 $f(n)$。

然后考虑上面的式子怎么求：
${\sum }_{i=1}^n{\sum }_{j=1}^{m}g(gcd(i,j))$
$={\sum }_{d=1}^{min(n,m)}g(d){\sum }_{i=1}^n{\sum }_{j=1}^m[gcd(i,j)=d]$
$={\sum }_{d=1}^{min(n,m)}g(d){\sum }_{i=1}^{\lfloor \frac{n}{d}\rfloor }{\sum }_{j=1}^{\lfloor \frac{m}{d}\rfloor }[gcd(i,j)=1]$
$={\sum }_{d=1}^{min(n,m)}g(d){\sum }_{k=1}^{min(\lfloor \frac{n}{d}\rfloor ,\lfloor \frac{m}{d}\rfloor )}\mu (k)\times \lfloor \frac{n}{dk}\rfloor \times \lfloor \frac{m}{dk}\rfloor$
$={\sum }_{T=1}^{min(n,m)}\lfloor \frac{n}{T}\rfloor \times \lfloor \frac{m}{T}\rfloor {\sum }_{d|T}g(d)\times \mu (\frac{T}{d})$
设 $F(T)={\sum }_{d|T}g(d)\times \mu (\frac{T}{d})$

那么我们需要维护出来 $F$ 的前缀和。
每次新加入一个 $d$ 就把它的所有倍数 $T$ 加上$f(d)\times \mu (\frac{T}{d})$。那么我们需要一个单点修改，区间求和的数据结构。树状数组就可以。时间复杂度是 调和级数 加上树状数组的复杂度。 $O(n{\log }^{2}n+Q\sqrt{n}\log n)$。
CODE：

#include<bits/stdc++.h>
#define int long long
using namespace std; // 首先容易求出 f(d)， 然后离线就好了 
const int N = 1e5 + 10;
const int mod = (1LL << 31);
int n, m, q;
int mu[N], prime[N], tot, idx[N];
bool vis[N];
int f[N], F[N], c[N], ans[N];
struct qq {
	int n, m, v, id;
}qc[N];
int lowbit(int x) {return x & -x;}
void add(int x, int y) {
	for(; x < N; x += lowbit(x)) c[x] = (c[x] + y) % mod;
}
int ask(int x) {
	int res = 0;
	for(; x; x -= lowbit(x)) res = (res + c[x]) % mod;
	return res;
}
void pre() {
	mu[1] = 1;
	for(int i = 2; i < N; i ++ ) {
		if(!vis[i]) {prime[++ tot] = i; mu[i] = -1;}
		for(int j = 1; i * prime[j] < N && j <= tot; j ++ ) {
			vis[i * prime[j]] = 1;
			if(i % prime[j] == 0) {
				mu[i * prime[j]] = 0;
				break;
			}
	    	mu[i * prime[j]] = -mu[i];
		}
	}
	for(int i = 1; i < N; i ++ ) {
		for(int j = 1; j * i < N; j ++ ) {
			f[j * i] = (f[j * i] + (i)) % mod;
		}
	}
}
bool cmp(qq x, qq y) {
	return x.v < y.v;
}
bool cmpf(int x, int y) {
	return f[x] < f[y];
}
void Add(int x) { // 加入下标为x的 
	for(int i = 1; i * x < N; i ++ ) {
		add(i * x, (f[x] * mu[i] + mod) % mod);
	}
}
int calc(int n, int m) {
	int t = min(n, m);
	int l = 1, r; int res = 0;
	while(l <= t) {
		r = min({n / (n / l), m / (m / l), t});
		res = (res + (1LL * ((ask(r) - ask(l - 1)) % mod) * (n / l) % mod * (m / l) % mod) + mod) % mod;
		l = r + 1;
	}
	return res;
} 
signed main() {
	pre();
	scanf("%lld", &q);
	for(int i = 1; i <= q; i ++ ) {
		int v; scanf("%lld%lld%lld", &n, &m, &v);
		qc[i] = (qq) {n, m, v, i};
	}
	sort(qc + 1, qc + q + 1, cmp);
	for(int i = 1; i < N; i ++ ) idx[i] = i;
	sort(idx + 1, idx + N, cmpf);
	int now = 1;
	for(int i = 1; i <= q; i ++ ) {
		while(now < N && f[idx[now]] <= qc[i].v) {
			Add(idx[now]);
			now ++;
		}
		ans[qc[i].id] = calc(qc[i].n, qc[i].m);
	}
	for(int i = 1; i <= q; i ++ ) printf("%lld\n", ans[i]);
	return 0;
}

练习题

51nod 1675 序列变换

点这里
题意：
给你两个长度为 $n$ 的序列 $a,b$，求有多少对 $(x,y)$，满足以下两个条件：

1. $gcd(x,y)=1$
2. $a_{b_x}=b_{a_y}$

$1\le n\le 10^5,1\le a_i,b_i\le n$

BZOJ3561 DZY Loves Math VI

点这里
题意：
给定正整数 $n,m$，求：${\sum }_{i=1}^n{\sum }_{j=1}^{n}lcm(i,j{)}^{gcd(i,j)}$
$1\le n,m\le 5\times 10^5$

[bzoj3309]DZY Loves Math

点这里
题意：
对于正整数 $n$，定义 $f(n)$ 为 $n$ 所含质因子的的最大幂指数。特别的 $f(1)=0$
$T$ 组询问，每次给定 $a,b$，求 ${\sum }_{i=1}^a{\sum }_{j=1}^{b}f(gcd(i,j))$
$1\le T\le 10^4,1\le a,b\le 10^7$

[bzoj4816–Sdoi2017] 数字表格

点这里
题意：
$f(n)$ 表示斐波那契第 $n$ 项。
$T$ 组询问，每次给定 $n,m$。求 ${\prod }_{i=1}^n{\prod }_{j=1}^{m}f[gcd(i,j)]$。答案对$10^9+7$ 取模。
$1\le T\le 1000,1\le n,m\le 10^6$

[hdoj4746]Mophues

点这里
题意：
$Q$ 组询问，每次给你 $n,m,p$。求 ${\sum }_{i=1}^n{\sum }_{j=1}^m[gcd(i,j)\le p]$
$1\le Q\le 5\times 10^3,2\le n,m,p\le 5\times 10^5$

技巧总结

1. 遇到与 $gcd$ 有关的式子可以考虑莫比乌斯反演
2. 把枚举 $gcd$ 的式子提前是常见思路
3. 遇到需要二次分块或者 分母是两个变量乘积 的情况，可以考虑交换枚举顺序，先枚举乘积。
4. 遇到对 $gcd$ 的大小有限制的题目可以考虑离线，把 $gcd$ 由小到大依次加入。