我来填坑啦

积性函数

若对于定义在正整数集上的成立时,则称为积性函数,若满足但不要求则称为完全积性。

性质:积性函数的卷积还是积性函数

积性函数通常可以由线性筛求得。

常见积性函数

欧拉函数
表示的约数的次幂和
表示的约数的个数
莫比乌斯函数
狄利克雷卷积的乘法单位元 完全积性
单位函数 完全积性
恒等函数 完全积性
做题的时候不知道是不是积性函数可以打个表大胆猜测一下

莫比乌斯函数的性质

对于任意正整数有:

常作为容斥的系数来考虑。

狄利克雷卷积

数论函数的狄利克雷卷积定义为
狄利克雷卷积满足交换律、结合律,对加法满足分配律,存在单位元函数使得
例如: * * *

一些技巧

因为 有很多相同的值,因此可以数论分块,可以证明最多分成块。

莫比乌斯反演

公式:
证明:
形式二:
形式二一般比较常用

一些傻逼的例子&莫比乌斯反演的应用

所有式子默认,若不满足则交换。

对于一些函数,如果我们很难直接求出他们的值,而容易求出他们的倍数和或约数和,那么我们可以通过莫比乌斯反演来求

1D Gcd Sum :

2D Gcd Sum :

2D Prime Sum :

1D Prime Sum :

1D Lcm Sum :
因为有 因此

2D Lcm Sum : 我们选择枚举且设,则有,继续定义那么我们可以得出时间复杂度,此式还可以进一步优化但我实在写不动了,坑了

2D Gcd = k Sum : 我们设的个数,设的个数,则有关系,易得,然后直接上莫比乌斯反演得,显然即为所求,我们采用数论分块的方式就可以降到

莫比乌斯反演应该还有些操作,懒得写了,坑了

杜教筛

步入正题

首先掏出tls的blog
杜教筛的学习要点by冯爷:给一个已知积性函数配一个积性函数卷积后的积性函数的前缀和很好算。
杜教筛的学习要点byzbh:要会算时间复杂度。zbh爷表示非常bs博客说成高阶无穷小量而不证复杂度的,强行积分证复杂度QAQ
常见的积性函数可以自觉回到上面去看。

给出杜教筛的一般形式

比如说要求一个积性函数的前缀和,即,我们就可以找个积性函数,把做一个卷积,再求一下卷积的前缀和,把提出来操作一番因此我们可以得到我们发现等号右边的前面的这个玩意是一个狄利克雷卷积,因此有*
如果狄利克雷卷积的前缀和非常好算的话,那么我们就可以对后面的东西进行数论分块,然后递归计算。记得要记忆化搜索,其实也能跑得飞快(雾

按照jiry_2说的应该有两种形式,转自jiry_2's blog
* 为完全积性函数
则有 * *
*
则有 *

杜教筛例题1

其中
这个公式也可以看成 定义,于是

显得有点乱,但是我又不会排版QAQ
考虑计算出值,就可以计算出,现在来算算时间复杂度。设,运用微积分的知识简单算算可以得到,但是呢因为本身是一类积性函数的前缀和,可以用筛法解决一部分,假设处理到,则复杂度变为 使解得时,复杂度可取到最小为

杜教筛例题2

其中
,我们套用上面杜教筛的一般模板得到,同时我们知道的前缀和是,因此,得到

写在最后,不要因为知道杜教筛和线性筛就tm老想筛,有时候暴力的埃氏筛也不错QAQ

一些题目

莫比乌斯函数之和
利用
欧拉函数之和
利用
BZOJ 3944 Sum
貌似就是上面两道题的总和,注意要一块算不然会T
51nod 最小公倍数之和3





观察到实际上就是



接下来我们需要求的前缀和,丢两个卷进去


所以有

发表评论

电子邮件地址不会被公开。 必填项已用*标注