莫比乌斯函数
写在前面
这篇文字从前缀和的角度来推导莫比乌斯函数。
一维前缀和
给出G(i)所有的函数值,要求F(i)某一个指定的函数值。
这个大家都会求:
二维前缀和
给出G(i,j)所有的函数值,求F(i)某一指定函数值。
这个大家勉强可以记起来,用一个容斥原理:
高维前缀和
先想象一个三维的前缀和。
接下来我们在想象四维、五维的前缀和?
感觉有点晕。
但是凭借三维前缀和、二维前缀和以及一维前缀和的性质,我们似乎不难得到这样一个基于容斥原理的想法。
题目要求一致,同样给出G(p[1],p[2],p[3],……,p[k]),求F(p[1],p[2],p[3],……p[k])。
(由于OI关系,接下来的一些函数表达式可能会用数组的写法,有些可能不会很规范)
有;
于是:
从高维前缀和的启发
从F推导出G,称之为一个变换。
从G推导出F,称之为一个反演。
另一种一维前缀和
给出下面的一个函数:
给出所有的G(1),G(p),G(p^2),G(p^3)……,求F(1),F(p),F(p^2),F(p^3)……
不难发现:
G(1)=F(1)
G(p)=F(1)+F(p)
G(p^2)=F(1)+F(p)+F(p^2)
……
于是可以得到,G为F在某种意义上的前缀和。
那么对于问题而言:
另一种高维前缀和
同样这个函数:
如果限定n=p[1]^e[1]*p[2]^e[2],其中p[1]与p[2]是质数。那么做一次反演,我们就可以得到:
另一种形式的高维前缀和
由于任何一个数都可以质因数分解(除了1,我们自动忽略1好了),于是我们可以把这个式子按照类似高维前缀和一样推广下去:
给出函数G,做一次变换,得到:
(第三次出现这个式子,但是现在它已经是没有任何限定的了)
做一次反演,得到
由上面的对应关系,可以发现。
显然d|n。
而末尾还有一部分(-1)的次幂。我们现在对此进行讨论:
我们把后面这一部分记为另一个函数:
为什么参数是n/d呢?因为如果n/d确定了,那么指数sigma(k[i])也就确定了。由此我们可以把参数设置为n/d。
换一个表达形式:
接下来这个函数的值就很清楚了。
由于在我们的分析中,k[i]始终属于{0,1}。因此如果这个函数的自变量分解质因数以后,出现了某一个质因子的2次方以及2次方以上。我们就令此函数为0。这样在反演过程中,sigma式子中不会计算到任何值。
如果自变量分解质因数全部都是一次幂,那么我们数出有多少个质因数(在上面的式子(“换一个表达形式”这句话后面的那个式子)中即为m)。如果m为奇数,那么sigma(k[i])即为奇数,函数值为-1。如果m为偶数,函数值为1。
特别的,如果自变量为0,我们令函数值为1。这可以视为m=0,即偶数。
规范化的表达如下:
这就是莫比乌斯函数。
于是我们就得到了在网上经常看见的莫比乌斯函数的形式。
那么现在拥有了这一个函数,我们重新回顾变换与反演:
总算搞清楚一点莫比乌斯函数了。我本以为要搞一个晚上。看来是不必了。