[数学提高] 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;i1次, 因此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

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

数据范围:(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])

[数学提高] 1 莫比乌斯反演插图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 
using namespace std;
#define ll long long
typedef pair pii;
typedef pair pll;
#define xx first
#define yy second
#define ls (oo '9');
    do{x = x*10 + (ch-'0');ch = getchar();}while(ch>='0' && ch
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

文章来源于互联网:[数学提高] 1 莫比乌斯反演

THE END
分享
二维码