莫比乌斯反演

Asdfre

2026-08-12 12:39:17

发布于：广东

38阅读

0回复

0点赞

听起来很难，但其实跟着lyy仔细推一推感觉也还好的。。

莫比乌斯函数：

令 $n=\prod_{i=1}^{k}{p_i^{\alpha_i}}$ ，则：

$\mu(n) = \begin{cases} 1 & n = 1 \\ (-1)^k & n = p_1 p_2 \cdots p_k \text{（}p_i\text{ 为互异素数）} \\ 0 & \text{其他情况（}n\text{ 有平方因子）} \end{cases}$

狄利克雷卷积

定义两个函数 $f$ 和 $g$ 的卷积为 $(f*g)(n)$ ，则：

$(f*g)(n)=\sum_{d|n}{f(d)\times g(\frac{n}{d})}$

其具有的性质有：
1.交换律： $f*g=g*f$
2.结合律： $(f*g)*h=f*(g*h)$
3.分配律： $f*(g+h)=f*g+f*h$

一些函数

1. $\epsilon(n)$ ，又称单位函数。

$\epsilon(n)=[n=1]$

2. $I(n)$ ，又称常数函数。

$I(n)=1$

3. $Id_k(n)$

$Id_k=n^k，特别的Id_1=Id$

一些卷积恒等式

1. $\mu *I=\epsilon$ ，即

$\sum_{d|n} \mu(d) = [n=1]$

证明：

令 $n=\prod_{i=1}^{k}{p_i^{\alpha_i}}$ ， $n'=\prod_{i=1}^{k}{p_i}$ ，显然 $\sum_{d|n}{\mu(d)}=\sum_{d'|n}{\mu(d')}$ 。

接着考虑贡献，这就是一个组合数的问题，每个质因子选或不选：

$\sum_{d|n}{\mu(d)}=\sum_{i=1}^{k}{\binom{k}{i}}\times (-1)^k=(1-1)^k=0$

而且显然当 $n=1$ 时总和才会为 $1$

2. $\phi * I=Id$ ，证明：

按照定义带入： $\sum_{d|n}{\phi}(d)=n$ 看起来证明很复杂？~~其实我也不会~~，好吧，感觉思路听巧妙的。。

将所有分数： $\frac{1}{n},\frac{2}{n}...$ 化为最简分数，对于每个 $d|n$ 做分母，恰好有一个 $1\le k \le d$ 使得 $(k,d)=1$ ，所以有 $\phi(d)$ 个，得证。

3. $Id* \mu=\phi$ ，证明：

由 $\mu*I=\epsilon$ ，将式子 $\phi*I=Id$ 同时卷积上 $\mu$ ，则：

$\phi * I * \mu=Id * \mu \implies \phi=Id*\mu$

得证。

当然还有更多，大部分用的少，有用到的在补吧。。

莫比乌斯反演

形式1：若 $g(n)=\sum_{d|n}{f(d)}$ ，即 $g=f*1$ ，则有：

$f(n)=\sum_{d|n}{\mu(d)\times g(\frac{n}{d})}$

证明用卷积很好证，这就不给了。

形式2：若 $g(n)=\sum_{n|d}{f(d)}$ ，则有：

$f(n)=\sum_{n|d}{\mu(\frac{d}{n})\times g(d)}$

这个证明挺难的，反正我不会，谁会踢我一下。。

线性筛求 $\phi$ 和 $\mu$

按照定义来就行，直接贴代码吧。

mu[1] = 1;
for (int i = 2; i < N ; ++i) {
	if (!is[i]) {
		primes[++ cnt] = i;
		mu[i] = -1;
	}
	for (int j = 1; j <= cnt && i * primes[j] < N; ++j) {
		is[i * primes[j]] = true;
		if (i % primes[j] == 0) {
			mu[i * primes[j]] = 0;
			break;
		}
		mu[i * primes[j]] = -mu[i];
	}
}

phi[1] = 1;
for (int i = 2; i < N ; ++i) {
	if (!is[i]) {
		primes[++cnt] = i;
		phi[i] = i - 1;
	}
	for (int j = 1; j <= cnt && i * primes[j] < N ; ++j) {
		is[i * primes[j]] = true;
		if (i % primes[j] == 0) {
			phi[i * primes[j]] = phi[i] * primes[j];
			break;
		}
		phi[i * primes[j]] = phi[i] * (primes[j] - 1);
	}
}

核心应用

考虑基础问题，用这个做一个引入：

$\sum_{i=1}^{n}\sum_{j=1}^{n}{[(i,j)=1]}=?$

我们可以将一个正方形分成两个三角形，每个三角形中一个数 $i$ ， $\forall j\le i$ 与 $i$ 互质的数恰好是有 $\phi(i)$ 个，当然 $\phi(1)$ 单独考虑。

所以：

$\sum_{i=1}^{n}\sum_{j=1}^{n}{[(i,j)=1]}=1+2\times \sum_{i=2}^{n}{\phi(i)}=2\times \sum_{i=1}^{n}{\phi(i)}-1$

当然这道题中你还要考虑 $(0,1)(1,0)$ 的两个情况。

那当 $n \not= m$ ：

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

显然刚刚的做法不可做了，那怎么办？

我们钦定 $n\le m$

考虑对 $(i,j)=1$ 做转化：

$[(i,j)=1] \implies \epsilon((i,j)=1) \implies \sum_{d|(i,j)}\mu(d) \implies \sum_{d|i,d|j}{\mu(d)}$

所以：

$\sum_{i=1}^{n}\sum_{j=1}^{m}{[(i,j)=1]}=\sum_{i=1}^{n}\sum_{j=1}^{m} \sum_{d|i,d|j}{\mu(d)}$

显然可以交换求和顺序：

$\implies \sum_{d=1}^{n} \sum_{i=1}^{n}[d|i]\sum_{j=1}^{m}{[d|j]}{\times \mu(d)} \implies \sum_{d=1}^{n} {\mu(d) \times \lfloor \frac{n}{d} \rfloor \times \lfloor \frac{m}{d} \rfloor}$

显然后面的那个东西可以用整除分块做，这样时间复杂度能做到 $\sqrt{N}$ 级别。

拓展1：给定 $k$ ， $\sum_{i=1}^{n}\sum_{j=1}^{m}{[(i,j)=k]}=?$

显然将 $k$ 提出去， $n$ 和 $m$ 间有 $\lfloor \frac{n}{k} \rfloor$ 和 $\lfloor \frac{m}{k} \rfloor$ 个 $k$ 的倍数（就跟上面的转化一样），变为：

$\sum_{i=1}^{\lfloor \frac{n}{k} \rfloor}\sum_{j=1}^{\lfloor \frac{m}{k} \rfloor}{[(i,j)=1]}$

套板子即可。

拓展2：求 $\sum_{i=1}^{n}\sum_{j=1}^{m} gcd(i,j)$ 。

根据 $Id=\phi * I$ 得， $gcd(i,j)=\sum_{d|i,d|j}{\phi(d)}$ 即可做完，可以自己推一下。

P2522 [HAOI2011] Problem b

显然一个容斥原理，画个图你们就明白了：

当然上下界自己想清楚。。。

#include <bits/stdc++.h>
using namespace std;
namespace CZW {
#define endl "\n"
#define vec std::vector
#define pb push_back
#define eb emplace_back
	using ll = long long;
	using ull = unsigned long long;
	using i128 = __int128;
	constexpr int N = 5e4 + 5;
	int primes[N], mu[N], cnt;
	ll sum[N];
	bool is[N];
	void init() {
//		freopen("1.in","r",stdin);
//		freopen("my.out","w",stdout);
		ios::sync_with_stdio(false);
		cin.tie(nullptr);
		cout.tie(nullptr);
		mu[1] = 1;
		for (int i = 2; i < N ; ++i) {
			if (!is[i]) {
				primes[++ cnt] = i;
				mu[i] = -1;
			}
			for (int j = 1; j <= cnt && i * primes[j] < N ; ++j) {
				is[i * primes[j]] = true;
				if (i % primes[j] == 0){
					mu[i * primes[j]] = 0;
					break;
				}
				mu[i * primes[j]] = -mu[i];
			}
		}
		for (int i = 1; i < N; ++i) sum[i] = sum[i - 1] + mu[i];
	}
	ll solve(int n, int m, int k){
		n /= k, m /= k;
		if (n > m) swap(n, m);
		int l = 1, r = 0;
		ll ans = 0;
		while (l <= n){
			r = min({n, n / (n / l), m / (m / l)});
			ans += (sum[r] - sum[l - 1]) * (n / l) * (m / l);
			l = r + 1;
		}
		return ans;
	}
	void Main() {
		int a, b, c, d, k;
		cin >> a >> b >> c >> d >> k;
		cout << solve(b, d, k) - solve(a - 1, d, k) - solve(b, c - 1, k) + solve(a - 1, c - 1, k) << endl;
	}
}
int main() {
	CZW::init();
	int Test = 1;
	cin >> Test;
	while (Test--)
		CZW::Main();
	return 0;
}

GCD

一道非常幽默的题，题解区都是欧拉函数的做法，但显然这也是一个莫比乌斯反演的板子，枚举 $[1,10^7]$ 质数，跑一个板子即可。

但你们可能想问复杂度不是 $O(\frac{n}{\log n}\sqrt{n})$ 吗，不是过不了吗？

但是你们想一下，每次枚举质数，单次复杂度是 $O(\sqrt{\frac{n}{p}})$ 的，算一下：

总复杂度：

$\sum_{p \le n} \sqrt{\frac{n}{p}} = \sqrt{n} \sum_{p \le n} \frac{1}{\sqrt{p}}$

根据素数定理和积分估计：

$\sum_{p \le n} \frac{1}{\sqrt{p}} \approx \int_{2}^{n} \frac{1}{\sqrt{t}} \cdot \frac{1}{\ln t} \, dt \approx \frac{2\sqrt{n}}{\ln n}$

所以总复杂度：

$\sqrt{n} \cdot \frac{2\sqrt{n}}{\ln n} = \frac{2n}{\ln n} \approx \frac{2 \times 10^7}{\ln(10^7)} \approx \frac{2 \times 10^7}{16.1} \approx 1.24 \times 10^6$

显然稳过，代码不放了，板子来的。

Crash数字表格

非常爽的推柿子，~~我还是太蒻了，推一半卡住了，还要别人提醒我一下~~。

求 $\sum_{i=1}^{n}\sum_{j=1}^{m}{lcm(i,j)}$ 。

令 $n\le m$

$\begin{aligned} \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_{i=1}^{n}\sum_{j=1}^{m}i\times j \sum_{d=1}^{n}{\frac{[gcd(i,j)=d]}{d}}\\ &=\sum_{d=1}^{n}\sum_{i=1}^{n}\sum_{j=1}^{m}i\times j\times \frac{[gcd(i,j)=d]}{d}\\ &=\sum_{d=1}^{n}\sum_{x=1}^{\lfloor \frac{n}{d} \rfloor} \sum_{y=1}^{\lfloor \frac{m}{d} \rfloor} {x\times y \times d^2\times \frac{[gcd(x,y)=1]}{d}}\\ &=\sum_{d=1}^{n}\sum_{x=1}^{\lfloor \frac{n}{d} \rfloor} \sum_{y=1}^{\lfloor \frac{m}{d} \rfloor} {x\times y \times d\times [gcd(x,y)=1]}\\ &=\sum_{d=1}^{n}\sum_{x=1}^{\lfloor \frac{n}{d} \rfloor} \sum_{y=1}^{\lfloor \frac{m}{d} \rfloor} {x\times y \times d\sum_{k|x,k|y}{\mu(k)}}\\ &=\sum_{d=1}^{n}\sum_{x=1}^{\lfloor \frac{n}{d} \rfloor} \sum_{y=1}^{\lfloor \frac{m}{d} \rfloor} {x\times y \times d\sum_{k=1}^{\lfloor \frac{n}{d} \rfloor}{\mu(k)[k|x][k|y]}}\\ &=\sum_{d=1}^{n}d\sum_{k=1}^{\lfloor \frac{n}{d} \rfloor}\mu(k)\sum_{i\times k=1}^{\lfloor \frac{n}{d} \rfloor}i \times k\sum_{j\times k=1}^{\lfloor \frac{m}{d} \rfloor} j\times k\\ &=\sum_{d=1}^{n}d\sum_{k=1}^{\lfloor \frac{n}{d} \rfloor}\mu(k)\sum_{i=1}^{\lfloor \frac{n}{d\times k} \rfloor}i\sum_{j=1}^{\lfloor \frac{m}{d\times k} \rfloor} j\\ \end{aligned}$

令 $f1(n,m)=\sum_{i=1}^{n}i\sum_{j=1}^{m}j$ ，显然可以 $O(1)$ 算。

再令 $f2(n,m)=\sum_{i=1}^{n}\mu(i)\times f1(\lfloor \frac{n}{i} \rfloor,\lfloor \frac{m}{i} \rfloor)$ ，显然对 $f1(\lfloor \frac{n}{i} \rfloor,\lfloor \frac{m}{i} \rfloor)$ 这个东西当每块定值，进行整除分块。

最后再对整体来一个整除分块即可。

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <unordered_map>
#include <set>
//#include <bits/stdc++.h>
using namespace std;
namespace CZW {
#define endl "\n"
#define vec std::vector
#define pb push_back
#define eb emplace_back
	using ll = long long;
	using ull = unsigned long long;
	using i128 = __int128;
	constexpr ll mod = 20101009, N = 1e7 + 5, inv2 = (mod + 1) / 2;
	int primes[N], mu[N], cnt;
	ll sum[N];
	bool is[N];
	void init() {
//		freopen("1.in","r",stdin);
//		freopen("my.out","w",stdout);
		ios::sync_with_stdio(false);
		cin.tie(nullptr);
		cout.tie(nullptr);
		mu[1] = 1;
		for (int i = 2; i < N ; ++i) {
			if (!is[i]) {
				primes[++ cnt] = i;
				mu[i] = -1;
			}
			for (int j = 1; j <= cnt && i * primes[j] < N; ++j) {
				is[i * primes[j]] = true;
				if (i % primes[j] == 0) {
					mu[i * primes[j]] = 0;
					break;
				}
				mu[i * primes[j]] = -mu[i];
			}
		}
		for (int i = 1; i < N; ++i) sum[i] = (sum[i - 1] + mu[i] * i % mod * i % mod) % mod;
//		for (int i = 1; i < 1000; ++i) cout << mu[i] << ' ' << sum[i] << endl;
	}
	void Main() {
		auto f1 = [&](int n, int m)->ll{
			return 1ll * n * (n + 1) % mod * inv2 % mod * m % mod * (m + 1) % mod * inv2 % mod;
		};
		auto f2 = [&](int n, int m)->ll{
			if (n > m) swap(n, m);
			int l = 1, r = 0;
			ll ans = 0;
			while (l <= n) {
				r = min({n, n / (n / l), m / (m / l)});
				ans = (ans + ((sum[r] - sum[l - 1]) % mod + mod) % mod * f1(n / l, m / l) % mod) % mod;
				l = r + 1;
			}
			return ans;
		};
		auto f3 = [&](int n, int m)->ll{
			if (n > m) swap(n, m);
			int l = 1, r = 0;
			ll ans = 0;
			while (l <= n) {
				r = min({n, n / (n / l), m / (m / l)});
				ans = (ans + f2(n / l, m / l) * (l + r) % mod * (r - l + 1) % mod * inv2 % mod) % mod;
//				cout << ans << endl;
				l = r + 1;
			}
			return ans;
		};
//		cout << f1(5, 6) << endl;
		int n, m;
		cin >> n >> m;
		cout << f3(n, m);
	}
}
int main() {
	CZW::init();
	int Test = 1;
//	cin >> Test;
	while (Test--)
		CZW::Main();
	return 0;
}

约数和

想做出这道题，有一个非常重要的结论， $d$ 为积性函数。

所以对于 $d(i\times j)$ ，枚举 $i$ 和 $j$ 的因子，若 $gcd(x,y)=1$ 则其必然为 $i\times j$ 的一个答案贡献，即：

$d(i\times j)=\sum_{x|i}\sum_{y|j}[gcd(x,y)=1]$

既然这样很显然就可以开始推柿子了（建议自己推一下）

$\begin{aligned} \sum_{i=1}^{n}\sum_{j=1}^{m}d(i\times j)&=\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{x|i}\sum_{y|j}[gcd(x,y)=1]\\ &=\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{x=1}^{n}\sum_{y=1}^{m}[x|i][y|j][gcd(x,y)=1]\\ &=\sum_{x=1}^{n}\sum_{y=1}^{m}\sum_{i=1}^{\lfloor \frac{n}{x} \rfloor}\sum_{j=1}^{\lfloor \frac{m}{y} \rfloor} [gcd(x,y)=1]\\ &=\sum_{x=1}^{n}\sum_{y=1}^{m}\sum_{i=1}^{\lfloor \frac{n}{x} \rfloor}\sum_{j=1}^{\lfloor \frac{m}{y} \rfloor}\sum_{d|x,d|y}{\mu(d)}\\ &=\sum_{d=1}^{n}\sum_{x=1}^{\lfloor \frac{n}{d} \rfloor}\sum_{y=1}^{\lfloor \frac{m}{d} \rfloor} \sum_{i=1}^{\lfloor \frac{n}{d \times x} \rfloor}\sum_{j=1}^{\lfloor \frac{m}{d \times y} \rfloor} \mu(d)\\ &=\sum_{d=1}^{n}\mu(d)\sum_{x=1}^{\lfloor \frac{n}{d} \rfloor} \lfloor \frac{n}{d\times x} \rfloor \sum_{y=1}^{\lfloor \frac{m}{d} \rfloor} \lfloor \frac{m}{d\times y} \rfloor \end{aligned}$

令 $f(i)=\sum_{j=1}^{i}\lfloor \frac{i}{j} \rfloor$ ，显然这个东西可以 $O(N\sqrt{N})$ 预处理。

然后还是对后面的东西进行整除分块即可。

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <unordered_map>
#include <set>
//#include <bits/stdc++.h>
using namespace std;
namespace CZW {
#define endl "\n"
#define vec std::vector
#define pb push_back
#define eb emplace_back
	using ll = long long;
	using ull = unsigned long long;
	using i128 = __int128;
	constexpr int N = 5e4 + 5;
	int primes[N], mu[N], cnt;
	bool is[N];
	ll f[N], sum[N];
	void init() {
//		freopen("1.in","r",stdin);
//		freopen("my.out","w",stdout);
		ios::sync_with_stdio(false);
		cin.tie(nullptr);
		cout.tie(nullptr);
		mu[1] = 1;
		for (int i = 2; i < N; ++i) {
			if (!is[i]) {
				primes[++cnt] = i;
				mu[i] = -1;
			}
			for (int j = 1; j <= cnt && i * primes[j] < N; ++j) {
				is[i * primes[j]] = true;
				if (i % primes[j] == 0) {
					mu[i * primes[j]] = 0;
					break;
				}
				mu[i * primes[j]] = -mu[i];
			}
		}
		for (int i = 1; i < N; ++i) sum[i] = sum[i - 1] + mu[i];
		auto get = [&](int n)->ll{
			int l = 1, r = 0;
			ll ans = 0;
			while (l <= n) {
				r = min(n, n / (n / l));
				ans += 1ll * (r - l + 1) * (n / l);
				l = r + 1;
			}
			return ans;
		};
		for (int i = 1; i < N; ++i) {
			f[i] = get(i);
		}
//		for (int i = 1; i <= 10; ++i) cout << f[i] << ' ';
//		cout << endl;
	}
	void Main() {
		int n, m;
		cin >> n >> m;
		if (n > m) swap(n, m);
		int l = 1, r = 0;
		ll ans = 0;
		while (l <= n) {
			r = min({n, n / (n / l), m / (m / l)});
			ans += (sum[r] - sum[l - 1]) * f[n / l] * f[m / l];
			l = r + 1;
		}
		cout << ans << endl;
	}
}
int main() {
	CZW::init();
	int Test = 1;
	cin >> Test;
	while (Test--)
		CZW::Main();
	return 0;
}

有帮助，赞一个

去预览

0/2000

全部评论 7

Xylophone
置顶
怎么是，唐氏莫反

1周前来自广东
1
- Eucatastrophe‌
  回复
  Xylophone
  数论的一生之敌
  
  1周前来自浙江
  1
- Asdfre
  回复
  Xylophone
  绷不住了
  
  1周前来自广东
  0
🥥
您怎么这么强！

1周前来自上海
1
- Asdfre
  回复
  🥥
  wu
  
  1周前来自广东
  0
Eucatastrophe‌
@yanghongzheng

1周前来自浙江
1
- yanghongzheng
  回复
  Eucatastrophe‌
  ?
  
  4天前来自北京
  0
cjdst
不要更新BSGS

6天前来自浙江
0
- cjdst
  回复
  cjdst
  我学不会，，，
  
  6天前来自浙江
  0
- cjdst
  回复
  cjdst
  我好弱
  
  6天前来自浙江
  0
cjdst
，，，

6天前来自浙江
0
Asdfre
@cjdst @wcqk @yezi @Xylophone
@prediction
欢迎来完成莫比乌斯反演大学习！

1周前来自广东
0
- wcqk
  回复
  Asdfre
  orz您怎么这么强
  
  1周前来自浙江
  1
- Asdfre
  回复
  wcqk
  wu
  
  1周前来自广东
  0
- prediction
  回复
  Asdfre
  您咋这强
  
  1周前来自浙江
  0
Asdfre
ddddddd

1周前来自广东
0