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

莫比乌斯反演

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

莫比乌斯函数

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_igeq 2\ (-1)^{k} & forall i,a_i=1 end{cases} ]

2. 性质

性质1

[sumlimits _{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})，其中(0leq b_ileq a_i)。

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

则(sumlimits _{d|n}mu(d)=sumlimits _{i=0}^kC_k^itimes(-1)^i)，又((a-b)^k=sumlimits_{i=0}^k C_k^i a^kb^{k-i})

((1-1)^k=sumlimits _{i=0}^kC_k^itimes (-1)^k)，故(sumlimits _{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)=sumlimits _{d|n}mu(d)=sumlimits _{d|n'}mu(d)\= sumlimits _{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)=sumlimits _{d|n}I(d)=sumlimits _{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=sumlimits_{d|n}f(d) Leftrightarrow f(n)=sumlimits _{d|n}mu(d)times F(frac n d))，

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

即(f(n)=sumlimits_{d|n}mu(d)times F(frac n d))。

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

(sumlimits_{d|n}mu(d)times F(frac n d)=sumlimits_{d|n}mu(d)times sumlimits_{i|frac n d}f(i)=sumlimits_{i|n}f(i)sumlimits_{d|frac n i}mu(d))

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

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

倍数形式：

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

证明：(sumlimits_{n|N}F(N)mu(frac N n)=sumlimits_{n|N}mu(frac N n)sumlimits _{N|i}f(i))

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

因此(sumlimits_{n|N}mu(frac N n)sumlimits _{N|i}f(i)=sumlimits_{d|frac i n}mu(d)sumlimits _{N|i}f(i))

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

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

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

p2522 Problem b

数据范围：(1leq n,kleq 5times 10^4;1leq aleq bleq 5times 10^4;1leq c leq d leq 5times 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])。

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

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

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

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

(f(k)=sumlimits_{t}mu(t)lfloor frac a {tk} rfloortimes 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("%lldn", 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)，求(sumlimits _{i=1}^N sumlimits_{j=1}^M d(itimes j))

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

(sumlimits _{i=1}^N sumlimits_{j=1}^M d(itimes j)=sumlimits _{i=1}^N sumlimits_{j=1}^M sumlimits _{x|i} sumlimits_{y|j} [(x,y)=1])

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

则(itimes j=prod_{i=1}^k p_i^{a_i+b_i})，(d(itimes 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}])，或者(xin[p_1,p_1^{a_1}],y=1)

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

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

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

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

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

• 再化简(F)。

(F(n)=sumlimits _{i=1}^N sumlimits_{j=1}^M sumlimits _{x|i} sumlimits_{y|j} [n|(x,y)]=sumlimits _{x=1}^N sumlimits_{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)是没有关系的，我们可以把它提出来。那么，里面就变成了(sumlimits _{i=1}^{lfloor frac N x rfloor}sumlimits _{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)=sumlimits _{x=1}^N sumlimits_{y=1}^M lfloor frac N x rfloor lfloor frac M y rfloor [n|(x,y)]=sumlimits _{x'=1}^{lfloor frac N n rfloor}sumlimits _{y'=1}^{lfloor frac M n rfloor}lfloor frac N {nx'} rfloorlfloor frac M {ny'} rfloor)

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

(F(n)=sumlimits _{x'=1}^{N'} sumlimits_{y'=1}^{M'} lfloor frac {N'} {x'} rfloor lfloor frac {M'} {y'} rfloor=(sumlimits _{x'=1}^{N'} lfloor frac {N'} {x'} rfloor)times(sumlimits_{y'=1}^{M'} lfloor frac {M'} {y'} rfloor))

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

• 再求(f(1))

(f(1)=sumlimits _{d=1}^Tmu(d)h(lfloor frac N d rfloor)h(lfloor frac M d rfloor))

由于(h(x))只和(x)有关，所以可以再分一次块，因此每次查询复杂度(O(sqrt N))，总时间复杂度(O(Nsqrt 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("%lldn", res); }  int main(void){ 	int T; 	Mobius(N - 1); 	H(N - 1); 	T = read(); 	while (T--){ 		solve(); 	} 	 	return 0; }