[知识点]莫比乌斯反演模型进阶

BitTigerio 2017-12-08

哪来什么进阶QAQ,只不过是被虐得更惨了

总结了一下lc传授的套路与模型

一般来讲是求与gcd有关的。那么可以反演得到模型:

令f(d)为1<=x<=n,1<=y<=m且gcd(x,y)=d的数对(x,y)的个数

然后可以枚举d进行一波操作,然后再换个元,大概可以得到

[知识点]莫比乌斯反演模型进阶

通过预处理出g(x)和前缀和,分块去计算答案,以达到单次询问√n

至于这个处理g(x),我们通常用以下方法:

借鉴线性筛,分类操作

①x为质数时

②i与p互质时求i*p

③i%p==0时求i*p(此时break)

通常第三种情况我们需要使i*p=i1*py,此时i1与p互质,这样就可以转化为情况二去解决问题了

那么我们怎么求得i1以及y呢?简单粗暴可以暴力去除,最坏复杂度是O(logn)

我们还可以O(1)去求:

对于每一个数,记录它的最小质因数P[i]和它的幂K[i]

由于筛的时候每个数都会被它的最小质因数筛掉,所以在break之前,p为i*p的最小质因数

情况二的时候,P[i*p]=p,K[i*p]=1

情况三的时候,由于i*p已经记录最小质因数p了,只需将K[i*p]++就好了

当需要求情况三的时候,K数组里就是y,求i1可以再维护一个数组G[x]=P[x]K[x],只需要G初始设为1,在K[x]++的时候G[x]*=p就可以了

O(1)求出i1=(i*p)/G[i*p](撒花!!)

此类型题目:

[BZOJ 3529]数表