莫比乌斯反演


2016-11-16:
线性筛求 mobius 函数。把所有质数的 mu 值初始化为1,之后所有的数乘上一个质数就等于原数 mu 值取反。容易知若该数不为 square-free 则必仍为0不必特殊处理。注意到仅需处理 i > p_j (第j个质数)的情况,因为之后的可以由 i * p_maxj / p_i1 (能整除i的最小质数、i的第一个质因数)与 p_i1 筛到,不必重复筛。


很久之前的坑在下面

早上即兴讲这东西被全部人D了……果然我口才太烂了……得多练……


先来一道题大家做一下引入一下莫比乌斯函数……
给你一个数$ n $,求问$ 1-n $中是$ {2,3,5} $的倍数有多少个。
事实上是小学奥数的题。
做法很简单的吧……$$
lfloor frac{n}{2} rfloor+lfloor frac{n}{3} rfloor+lfloor frac{n}{5} rfloor-lfloor frac{n}{[2,3]} rfloor-lfloor frac{n}{[2,5]} rfloor-lfloor frac{n}{[3,5]} rfloor+lfloor frac{n}{[2,3,5]} rfloor
$$这样算出来就行了……
事实上就是一个容斥原理的典型的例子,看这幅图
【图】
这样就直观起来了。
但如果,我求的不只是2,3,5的倍数呢,项数变得很多很多怎么办呢?
你说:没关系,我枚举的完!
好你赢了……但如果我要查询的集合是一个无穷集呢?
你说:省略号大法好!
那有没有一点严谨点的方法呢……


好,其实我们纠结的原因就是确定符号的问题,也就是什么时候该加什么时候该减比较麻烦……
有人说看是现在的容斥的几个集合是奇数个还是偶数个就可以确定加减了!
呃,too young too simple!如果集合互为倍数就像{2,8}呢?


我们来讨论一下解决方法。
TBC……

标签: none

仅有一条评论

  1. %%%zfr
    催更?

添加新评论