神奇的莫比乌斯反演

如果你学过二元一次函数,只要知道其中一个未知量就可以求出另外一个。例如

    \[ y = x + 1 \]

你只要知道了x,就可以求出y。反过来,如果你知道y,也可以在移项之后求出另一项。

嗯,这太简单了,你觉得不过瘾,于是又看了看微积分,把原函数F(n)微分一下就得到导函数f(n)。 但只凭借f(n),多数情况下也能用积分轻松反求F(n)

想象一下,你熟练地操纵着微积分魔法,将自己的原函数和导函数两个水晶球互相交换,动作眼花缭乱,敌人被你吓得不敢近身,这感觉很是微妙。当然,你得小心

不过,如果给你辅助函数和目标函数的特殊关系式,让你能够用目标函数求出辅助函数,你怎样才能利用这条性质,反过来用辅助函数求出目标函数呢?这就是我们今天要说的。

莫比乌斯反演

只是听着名字就觉得是个很炫酷的魔法名字有没有啊?事实上它本身也非常神奇。

很多人一看到莫比乌斯可能先想到莫比乌斯环,这个不科学的物体只有一面,引起了无数人的兴趣。它的发现者是August Ferdinand Möbius,可以称他莫比乌斯先生。莫比乌斯先生也是酷炫,13岁前一直在家自学,23岁时已经在哥廷根大学跟随数学大师高斯学天文学了。也是这货,提出了莫比乌斯反演。

莫比乌斯反演需要用到莫比乌斯函数,但在这儿我们先说一下反演。

定理: F(n)和f(n)是定义在非负整数集合上的两个函数,并且满足条件:

    \[ F(n)=\sum_{d|n}f(d) \]

那么存在一个结论:

    \[ f(n)=\sum_{d|n}\mu(d)F(\lfloor\frac{n}{d}\rfloor) \]

看不懂的先别着急,我们先来分析第一个式子。

那个大开口朝右的M为求和函数,而下面的d|n表示d要能被n整除。这个式子的意思就是,F(n)等于所有的符合条件的f(d)相加,符合条件意味着f(d)中的d要能被n整除。

例如,设p1是质数,能被p1整除的只有p1自己和1了,那么:

    \[ F(p1) = f(1) + f(p1) \]

接着来看第二个式子。

其中\lfloorx\rfloor代表向下取整,\lfloor\frac{n}{d}\rfloor当然就是代表n除以d后的商了。 而u()就是我们大名鼎鼎的莫比乌斯函数了。

莫比乌斯函数在这儿先给出它的前几项,怎么求的先不管,毕竟我们现在是冲着酷炫的反演去的。

x1234
u(x)1-1-10

第二个式子的意思即为,f(n)等于所有符合条件的F(x)乘上莫比乌斯函数再相加,符合条件意味着d可以被n整除且x乘上d不能超过n。

同样,设p1是质数,能被p1整除的只有p1自己和1了,那么:

    \[ f(p1) = u(1)F(p1) + u(p1)F(1)  \]

莫比乌斯反演定理是否正确呢?我们不如来检验一下,

令f(x) = x,那么
 F(1) = f(1) = 1
 F(2) = f(1) + f(2) = 3
 F(3) = f(1) + f(3) = 4
 F(4) = f(1) + f(2) + f(4) = 7
 f(1) = u(4)F(1) = F(1) = 1 
 f(2) = u(1)F(2) + u(2)F(1) = F(2) - F(1) = 2
 f(3) = u(1)F(3) + u(3)F(1) = F(3) - F(1) = 3
 f(4) = u(1)F(4) + u(2)F(2) + u(4)F(1) = F(4) - F(2) = 4

诶,神了,居然和莫比乌斯那货说得一模一样。不过,眼见可能不为实,那莫比乌斯函数是不是有什么猫腻啊?该不会是和反演串通好了来欺骗大家吧?接下来,我们来继续解开莫比乌斯函数的神秘面纱。

莫比乌斯函数

x12345678910
u(x)1-1-10-11-1001

上表是莫比乌斯函数前10个数,大家能不能猜到第11个数字是什么呢?不要看下面,先花10秒想一想。

嗯,恭喜你成功浪费了10秒钟。其实莫比乌斯函数的规律是这样的

  • u(1) = 1
  • 如果x能被分解为k个互不相同素数相乘,那么u(k) = (-1)^k
  • 其它情况下u(x) = 0

在坐标系上看起来是这个样子的:

但这样看起来平淡无奇的函数,我们却能先悄悄解决掉辅助函数F(n),再让莫比乌斯函数和反演巧妙配合,一举肢解掉难缠的目标函数f(n)。

有趣的应用

再来说个有趣的应用。你可能听说过怎么求全体自然数的和,但你知道怎么快速求最小公倍数矩阵的和嘛?

你可以把矩阵理解为长方形的表格。

例如下面,从上往下为1~n行,从左往右为1~m行,那么第i行第j列就是数字i和数字j的最小公倍数。

1    2    3    4    5
2    2    6    4    10
3    6    3    12   15
4    4    12   4    20

那么任意给出一个n和m,最小公倍数矩阵的和是多少呢?

这还不简单,一个个算出来再加上不就行了嘛?

嗯,是可以这么做。但我们管这叫“暴力”,或者“大力出奇迹”。

这样的时间复杂度为(nm),当n和m很大时会算到你怀疑人生。假如n和m都是100,而你每算一个数字花10秒,你一共需要花(100*100*10)秒,大约一天的时间才能完成。

但学了莫比乌斯反演魔法后,可以节省大把时间,时间复杂度仅为(n+m),按照上面的计算方法,理论上你只需要不到一个小时就可以算完。然后你就可以在别人埋头苦算时,悠闲地喝茶,看报,泡妞了

啥,具体方法?在你修炼到某种境界之前,请不要点开这个按钮

Leave a Reply