什么是反演:
有函数(F(x)),令(G(s)=sum F(x)),其中x与s的关系自定,在已知(G)求(F)的过程叫反演。
集合反演:(xsubseteq s)
公式:(F(x)=sum_{ssubseteq x} (-1)^{|x|-|s|} imes G(s))
推导过程: 核心是容斥。
(1.)首先,当(x=s)那么所有(tsubseteq sF(t))都被加入,我们要把除了(x)之外的都删掉。
(2.)我们将(x)与(s)相差(1)的都减去,他们两两之间的交集会减两次,还要再加回,那么就变成了容斥的形式。
莫比乌斯反演:(x|s)
公式:(F(n)=sum_{d|n} mu (frac n d) imes G(d))
推导过程:与集合反演类似,但是更加复杂,核心也是容斥。
(step 1:)首先,(mu(frac n d))代表(G(x))要加入还是删除,类似于集合反演,我们想要找到在(d)与(n)的某种关系下固定的系数,对于集合是(|x|-|s|),对于莫比乌斯反演,我们选择(frac n d)。
我们令(x=frac n d),分类讨论:
(step 2:)若(t=1),即(n=d),我们必须选,于是(mu(1)=1)
(step 3:)若(t)是质数,是(n)变成“子集”的最小单位,我们把他删除,(mu (p)=-1)
(step 4:)若(t)是两个不同质数的乘积,那么(d)被这两个质数删了两次要加回,那么(mu(t)=1)。
(step5:)那么三个质数时呢 ,我们又要减去,现在又变成了容斥的形式,所以当(t)是(k)个不同质数的乘积时(mu(t)=(-1)^k)。
(step6:)我们发现整个过程已经完毕,那么其余(mu=0)。
总结-莫比乌斯函数:
(~~~~~~~~~~~~~~~mu(x)={egin{cases}{1~~~~~~~~~~(x=1)}\{(-1)^k~~(x=p_1 imes p_2 imescdots imes p_k)}\{0~~~~~~~~~~(others)}end{cases}})
一些公式:
(组合数可证)
(左面通分,同去掉分母(n),根据(n=sum_{d|n}varphi(d))反演可得)$$sum_{d|n}mu(frac n d)sigma(d)=1$$
(反演回去可得(sigma(n)=sum_{d|n} 1))
扩展-莫比乌斯反演的另一种形式:(s|x)
与原式一样容斥可得到。
应用:
求$$sum_{i=1}Nsum_{j=1}N gcd(i,j)$$
设(f(x))是(gcd=x)的数对个数,(g(x))是(gcd=k imes x)的数对个数,那么:
根据扩展: