[数学提高] 1 莫比乌斯反演

时间：2022-09-09 11:38:21

没想到吧，真的有莫比乌斯反演专题！我现在已经看不懂我当时在写什么了！

莫比乌斯函数

1. 定义

由唯一分解定理，可以将正整数\(n\)写成\(n= \prod_{i=1}^kp_i^{a_i} = p_1^{a_1}p_2^{a_2}..p_k^{a_k}\)的形式，莫比乌斯函数\(\mu(n)\)的定义为

\[\mu(n)=\begin{cases} 1 & n=1 \\ 0 & \exist i, a_i\geq 2\\ (-1)^{k} & \forall i,a_i=1 \end{cases} \]

2. 性质

性质1

\[\sum\limits _{d|n}\mu(d)=\begin{cases} 1 & n=1 \\ 0 & n \neq 1 \end{cases} \]

证明：设\(d\)为\(n\)的约数，则\(d=\prod_{i=1}^kp_i^{b_i}\)，其中\(0\leq b_i\leq a_i\)。

对于\(\mu(d)\)，如果\(\exist b_i\geq 2\)，则\(\mu(d)=0\)。因此，有贡献的\(\mu(d)\)一定为\(C_k^i\times(-1)^i\)，也就是每个质数最多取一次。

则\(\sum\limits _{d|n}\mu(d)=\sum\limits _{i=0}^kC_k^i\times(-1)^i\)，又\((a-b)^k=\sum\limits_{i=0}^k C_k^i a^kb^{k-i}\)

\((1-1)^k=\sum\limits _{i=0}^kC_k^i\times (-1)^k\)，故\(\sum\limits _{d|n}\mu(d)=0^k=0\)

3. 与其他数论函数的关系

(1) \(\mu * I = e\)

证明：设\(n=\prod_{i=1}^kp_i^{a_i}, n'=\prod_{i=1}^kp_i\)

则\((\mu*I)(n)=\sum\limits _{d|n}\mu(d)=\sum\limits _{d|n'}\mu(d)\\= \sum\limits _{i=0}^k(-1)^i\)

呃，等等，好像性质一已经证明过了啊。\((\mu*I)(n)=[n=1]=e\)，

因此，\(\mu\)是\(I\)的狄利克雷逆。

(2) \(\mu * id = \varphi\)

这个在基础篇的性质证明过了QWQ，不写辣

(3) \(\mu * d=I\)

证明：\((I*I)(n)=\sum\limits _{d|n}I(d)=\sum\limits _{d|n}1=d(n)\)

\(\therefore d=I*I\)，又\(\mu=I^{-1}\)

\(\therefore \mu * d=I\)

4. 线性筛法求莫比乌斯函数
void Mobius(int n){
	mu[1] = 1;
	for (int i=2;i<=n;++i){
		if (!st[i]) p[++cnt] = i, mu[i] = -1;
		for (int j=1;p[j]<=n/i;++j){
			st[p[j] * i] = true;
			if (i % p[j] == 0) break;
			mu[p[j] * i] = -mu[i];
		}
	}
}
// 当i为质数时, 显然mu[i]=-1
// 当p[j]为i的最小质数时, 就说明p[j]这个质数出现了>1次, 因此mu[i * p[j]] = 0
// 否则
// (1) mu[i]=0, mu[p[j] * i] = 0
// (2) mu[i]不为0, p[j] * i就相当于增加了一个质数, 因此mu[p[j] * i] = -mu[i]

莫比乌斯反演

莫反的函数定义和转换过程大多依靠平时积累，见过类似套路，就会，没见过，就寄。

1. 定义

设\(f(n)\)为数论函数(定义在正整数集合上的函数)

因数形式：

  • \(F(n)=f*I=\sum\limits_{d|n}f(d) \Leftrightarrow f(n)=\sum\limits _{d|n}\mu(d)\times F(\frac n d)\)，

证明（利用狄利克雷卷积）：因为\(F(n)=f*I\)，则\(f=F*I^{-1}=F*\mu\)

即\(f(n)=\sum\limits_{d|n}\mu(d)\times F(\frac n d)\)。

证明（利用性质1+二重积分交换次序的思想）：

\(\sum\limits_{d|n}\mu(d)\times F(\frac n d)=\sum\limits_{d|n}\mu(d)\times \sum\limits_{i|\frac n d}f(i)=\sum\limits_{i|n}f(i)\sum\limits_{d|\frac n i}\mu(d)\)

（\(i\)能取到所有\(d\)可以取到的取值，这样反过来看，把\(i\)提到前面）

又当且仅当\(n=i\)时，\(\sum\limits_{d|\frac{n}i}\mu(d)=1\)，因此\(\sum\limits_{d|n}\mu(d)\times F(\frac n d)=f(n)\)

倍数形式：

  • \(F(n)=\sum\limits_ {n|N}f(N) \Leftrightarrow f(n)=\sum\limits_{n|N}F(N)\mu(\frac N n)\)，（枚举\(N\)为\(n\)的所有倍数，\(N\in[n,+\infin)\)）

证明：\(\sum\limits_{n|N}F(N)\mu(\frac N n)=\sum\limits_{n|N}\mu(\frac N n)\sum\limits _{N|i}f(i)\)

设\(d=\frac N n\)，则\(N=dn\)，则\(dn|i\)，即\(d|\frac i n\)

因此\(\sum\limits_{n|N}\mu(\frac N n)\sum\limits _{N|i}f(i)=\sum\limits_{d|\frac i n}\mu(d)\sum\limits _{N|i}f(i)\)

又当且仅当\(n=i\)时，\(\sum\limits_{d|\frac{n}i}\mu(d)=1\)，因此\(f(n)=\sum\limits_{n|N}F(N)\mu(\frac N n)\)

运用莫反的时候，通常都是因为\(F(n)\)好求，但是\(f(n)\)不好求，因此将\(f(n)\)用\(F,\mu\)表示出来。

2. 应用1：莫反+整数分块

p2522 Problem b

[数学提高] 1 莫比乌斯反演

数据范围：\(1\leq n,k\leq 5\times 10^4;1\leq a\leq b\leq 5\times 10^4;1\leq c \leq d \leq 5\times 10^4\)

思路：详细的整理一下吧。

首先，题目要我们求的东西，可以先拆成一个二维前缀和，\(A[a,b][c,d]=A[1,b][1,d]-A[1,b][1,c-1]-A[1,a-1][1,d]+A[1,a-1][1,c-1]\)。

[数学提高] 1 莫比乌斯反演

设\(f(k)=\sum\limits _{x=1}^a\sum\limits _{y=1}^b[(x,y)=k]\)，然后我们方便求的是这个\(F(k)=\sum\limits _{x=1}^a\sum\limits _{y=1}^b[k|(x,y)]\)，且\(F(k)=\sum\limits _{k|N}f(N)\)

则代入莫反倍数形式得\(f(k)=\sum\limits _{k|N}\mu(\frac N k) F(N)\)

先求\(F(N)\)。首先，\(N|(x,y)\)，也就是说，\(N|x,N|y\)，因此所有满足条件的点对数量为\(\lfloor \frac a N \rfloor\times \lfloor \frac b N \rfloor\)

则\(f(k)=\sum\limits _{k|N}\mu(\frac N k)\lfloor \frac a k \rfloor\times \lfloor \frac b k \rfloor\)，设$t=\frac N k \(，显然枚举\)t$的结果为\(1,2,..,\)这样的整数，\(N=tk\)。

\(f(k)=\sum\limits_{t}\mu(t)\lfloor \frac a {tk} \rfloor\times \lfloor \frac b {tk} \rfloor\)，再运用整数分块的知识进行求解即可，注释都写在代码里吧。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> pii;
typedef pair<ll,ll> pll;
#define xx first
#define yy second
#define ls (oo << 1)
#define rs (oo << 1 | 1)
#define PI acos(-1.0)

ll read(void);

int n, cnt;
const int N = 5e4 + 5; 
int p[N], mu[N];
int pre[N];
bool st[N];

//求Mobius函数和前缀和(分块的时候用)
void Mobius(int n){
	mu[1] = 1;
	for (int i=2;i<=n;++i){
		if (!st[i]) p[++cnt] = i, mu[i] = -1;
		for (int j=1;p[j]<=n/i;++j){
			st[p[j] * i] = true;
			if (i % p[j] == 0) break;
			mu[p[j] * i] = -mu[i];
		}
	}
	for (int i=1;i<=n;++i){
		pre[i] = pre[i - 1] + mu[i];
	}
}

ll f(int a, int b, int k){
    a /= k, b /= k;
	ll res = 0, n = min(a, b), l = 1, r;
    // 在[l,r]这段,(a/l)*(b/l)为定值,那么展开和式, 可以打包计算这一部分的和为(定值*mu的前缀和)
	while (l <= n){
		r = min(n, min(a / (a / l), b / (b / l)));
		res += 1LL * (pre[r] - pre[l - 1]) * (a / l) * (b / l);
		l = r + 1;
	}
	return res;
}

void solve(){
	int a, b, c, d, k;
	a = read(), b = read(), c = read(), d = read(), k = read();
    // 二维前缀和,或者说一个简单的容斥
	ll res = f(b, d, k) - f(b, c - 1, k) - f(a - 1, d, k) + f(a - 1, c - 1, k);
	printf("%lld\n", res);
}

int main(void){
	int T;
	Mobius(N - 1);
	T = read();
	while (T--){
		solve();
	}
	
	return 0;
}

ll read(void){
    ll x = 0, f=1;char ch;
    do{ch = getchar();if (ch == '-') f=-1;}while(ch<'0' || ch>'9');
    do{x = x*10 + (ch-'0');ch = getchar();}while(ch>='0' && ch<='9');
    return x*f;
}

/*
敬告kz: 
====================================
  1. 相信自己 
  2. 看清题意, 考虑清楚再动手 
  3.   **** 今天的数组有没有开小呀 ？ ****  **** 今天的数组有没有开小呀 ？ ****
  4. 是不是想复杂了？ 
  5. 数据溢出？
  6. 数组越界？边界情况？ 
  6. 不要犯低级错误！！！ 时间复杂度？空间复杂度？精度有没有问题？ 
====================================
* 提交的时候注意看编译器！c++17 / c++20 / python3 
*/
3. 应用2：莫反+提取公因数

p3327约数个数和 莫反+双分块

设\(d(x)\)为\(x\)的约数个数，给定\(T\)组\(n,m\)，求\(\sum\limits _{i=1}^N \sum\limits_{j=1}^M d(i\times j)\)

数据范围：\(1\leq N,M,T\leq 5\times 10^4\)

\(\sum\limits _{i=1}^N \sum\limits_{j=1}^M d(i\times j)=\sum\limits _{i=1}^N \sum\limits_{j=1}^M \sum\limits _{x|i} \sum\limits_{y|j} [(x,y)=1]\)

证明：设\(i=\prod_{i=1}^k p_i^{a_i},j=\prod_{i=1}^k p_i^{b_i}\)，\(0\leq a_i,b_i\)

则\(i\times j=\prod_{i=1}^k p_i^{a_i+b_i}\)，\(d(i\times j)=\prod_{i=1}^k(a_i+b_i+1)\)

即从\(i\)中选出约数\(x\)，\(j\)中选出约数\(y\)，对于\(p_1\)而言，若要求\((x,y)=1\)

则可以\(x=1,y=1\)，或者\(x=1,y=\in[p_1,p_1^{b_1}]\)，或者\(x\in[p_1,p_1^{a_1}],y=1\)

一共是\((a_1+b_1+1)\)种取法，其他质数同理。根据乘法原理，这些取法正好就是\(d(i\times j)\)。

  • 设出\(f(n),F(n)\)。

设\(f(n)=\sum\limits _{i=1}^N \sum\limits_{j=1}^M \sum\limits _{x|i} \sum\limits_{y|j} [(x,y)=n]\)，显然\(f(1)\)就是答案。

设\(F(n)=\sum\limits _{i=1}^N \sum\limits_{j=1}^M \sum\limits _{x|i} \sum\limits_{y|j} [n|(x,y)]\)，则\(F(n)=\sum\limits _{n|d}f(d)\)

即\(f(n)=\sum\limits _{n|d}\mu(\frac d n)F(d)\)令\(T=\min(N,M)\)，则\(f(1)=\sum\limits _{d=1}^T\mu(d)F(d)\)。

  • 再化简\(F\)。

\(F(n)=\sum\limits _{i=1}^N \sum\limits_{j=1}^M \sum\limits _{x|i} \sum\limits_{y|j} [n|(x,y)]=\sum\limits _{x=1}^N \sum\limits_{y=1}^M \lfloor \frac N x \rfloor \lfloor \frac M y \rfloor [n|(x,y)]\)

证明：首先，\(x|i,y|j\)，那么\(x,y\)肯定是能取到\([1,N],[1,M]\)的。当\(x,y\)固定后，\([n|(x,y)]\)和\(i,j\)是没有关系的，我们可以把它提出来。那么，里面就变成了\(\sum\limits _{i=1}^{\lfloor \frac N x \rfloor}\sum\limits _{j=1}^{\lfloor \frac M y \rfloor}1\)，也就是\(N,M\)里面有多少个\(i,j\)，它们是\(x,y\)的倍数，得证。

下面再消掉\([n|(x,y)]\)这个条件。

设\(x'=\lfloor \frac x n \rfloor,y'=\lfloor \frac y n \rfloor\)

\(F(n)=\sum\limits _{x=1}^N \sum\limits_{y=1}^M \lfloor \frac N x \rfloor \lfloor \frac M y \rfloor [n|(x,y)]=\sum\limits _{x'=1}^{\lfloor \frac N n \rfloor}\sum\limits _{y'=1}^{\lfloor \frac M n \rfloor}\lfloor \frac N {nx'} \rfloor\lfloor \frac M {ny'} \rfloor\)

令\(N'=\lfloor \frac N n \rfloor,M'=\lfloor \frac M n \rfloor\)

\(F(n)=\sum\limits _{x'=1}^{N'} \sum\limits_{y'=1}^{M'} \lfloor \frac {N'} {x'} \rfloor \lfloor \frac {M'} {y'} \rfloor=(\sum\limits _{x'=1}^{N'} \lfloor \frac {N'} {x'} \rfloor)\times(\sum\limits_{y'=1}^{M'} \lfloor \frac {M'} {y'} \rfloor)\)

令\(h(n)=\sum\limits_{i=1}^{n} \lfloor \frac {n} {i} \rfloor)\)，也就是标准整数分块，则\(F(n)=h(N')\times h(M')\)。

  • 再求\(f(1)\)

\(f(1)=\sum\limits _{d=1}^T\mu(d)h(\lfloor \frac N d \rfloor)h(\lfloor \frac M d \rfloor)\)

由于\(h(x)\)只和\(x\)有关，所以可以再分一次块，因此每次查询复杂度\(O(\sqrt N)\)，总时间复杂度\(O(N\sqrt N)\)。

int cnt;
const int N = 5e4 + 5;
int p[N], h[N], pre[N], mu[N];
bool st[N];

void Mobius(int n){
	mu[1] = 1;
	for (int i=2;i<=n;++i){
		if (!st[i]) p[++cnt] = i, mu[i] = -1;
		for (int j=1;p[j]<=n/i;++j){
			st[p[j] * i] = true;
			if (i % p[j] == 0) break;
			mu[p[j] * i] = -mu[i];
		}
	}
	for (int i=1;i<=n;++i){
		pre[i] = pre[i - 1] + mu[i];
	}
}

void H(int n){
	for (int i=1;i<=n;++i){
		for (int l=1, r;l<=i;l=r + 1){
			r = min(i, i / (i / l));
			h[i] += (r - l + 1) * (i / l); 
		}
	}
}

void solve(){
	int n, m;
	n = read(), m = read();
	ll res = 0;
	int k = min(n, m);
	for (int l=1, r;l<=k;l=r + 1){
		r = min(k, min(n / (n / l), m / (m / l)));
		res += (ll)(pre[r] - pre[l - 1]) * h[n / l] * h[m / l];
	}
	printf("%lld\n", res);
}

int main(void){
	int T;
	Mobius(N - 1);
	H(N - 1);
	T = read();
	while (T--){
		solve();
	}
	
	return 0;
}

相关文章