什么是反演
反演是对于满足$f(n)=sum_{k}a_{n,k}g(x)$的式子,我们已知$f()$求$g()$的一个过程我们称之为反演。通常来说一般的反演只能通过高斯消元来解决此类问题,但是对于对于一些特殊的反演我们可以通过一些特殊的方法来解出$g()$。例如二项式反演,莫比乌斯反演······
整除分块
简单来说就是$sum lfloor {xover i} rfloor$这玩意可以在$O(sqrt n)$的复杂度内求出。
具体来说就是对于含有$lfloor {xover i} rfloor$的求和式子($x$为常数)
对于任意一个$i(i le x)$,我们需要找到一个最大的$j(i le j le x)$,使得 $lfloor {xover i} rfloor = lfloor {xover j} rfloor$而$ j = {left lfloor { {lfloor {x over i}rfloor } over j} right rfloor} $
莫比乌斯函数
莫比乌斯函数是一种积性函数,其定义如下:
莫比乌斯函数存在如下性质:
我们还可以补充定义单位函数$varepsilon(n)=F(n)=sum_{d|n}mu(d)$
通过莫比乌斯函数是积性函数的性质,我们可以用线性筛或者其他数论中的筛子求出莫比乌斯函数的值。
1 |
bool vis[N]; |
莫比乌斯反演
由我们前文对反演的定义,我们来推导莫比乌斯反演。
我们已知函数
接着我们说一句废话
由莫比乌斯函数的性质我们可以将$varepsilon(n)$带入刚才的废话方程中:
展开得:
我们再来讨论${d|{nover m}}$,这堆东西可以化成$md|n$,所以也可以变成${m|{nover d}}$,所以上式可以化成:
然后后面这一块可以变成由$f()$来表示,故:
所以我们推出了莫比乌斯反演的公式就是:
$gcd$与莫比乌斯反演
在一些题目中我们会遇到一些带有$ gcd $的反演情况,通常都是求:
这样一个式子,或者是它的变形,为解决有关$ gcd $的问题我们不妨设$g(n,m)=sum_{i=1}^nsum_{j=1}^m[gcd(i,j)==k]$,很显然这个式子可以求但是复杂度是$O(n^2logn)$的,但是这样的复杂度我们并不能接受,我们可以尝试通过反演在$O(n)$的复杂度内解决。
我们首先考虑化简这个式子:
我们发现$[gcd(i,j)==1]$代入$varepsilon(n)$中再代入上式中式子的值不变,故我们将$[gcd(i,j)==1]$代入$varepsilon(n)$中再代入上式中。得:
改变求和顺序得:
(其中$d|i$表示当满足$d$整除$i$时,对答案有$1$的贡献)整理得:
近期评论