[关闭]
@xzyxzy 2018-02-05T01:25:12.000000Z 字数 798 阅读 678

线性筛

数论 小专题


引用

积性函数与线性筛_zsy
网上优秀博客
我也不知道什么是"莫比乌斯反演"和"杜教筛"_yyb
线性筛,积性函数,狄利克雷卷积,常见积性函数的筛法_yl
什么是卷积/我也没看懂但是应该会比较好懂/

正文

Part 1 积性函数都可以线性筛 ⊙ω⊙

一、积性函数

函数,若对于任意都有那么积性函数
若对于任意都有那么完全积性函数

二、线性筛

的时间内求解某个东西(比如说线性筛质数

三、常见积性函数

A、莫比乌斯函数Code

B、欧拉函数(留坑)

C、约数个数Article

D、约数和(留坑)

E、幂函数

F、狄利克雷卷积

  形如


  若都是积性函数那么也是积性函数,可以线性筛
  具体怎么筛请参见租酥雨's blog,典例参见该篇文章做题经验部分

Part 2不是积性函数也可以线性筛 >﹏<

一、比如说这个


题目来源:YY的GCD
题解:YYB博客链接

二、再看看这个


题目来源:Hillan and the girl
Code:Ubuntu Pastebin

三、这些非积性函数要具有一定性质才可以线性筛,所以不是很容易想到,暴力筛法在很多时候还是可以的

上面的一二式用暴力筛都能过,美其名曰埃氏筛法,就是从枚举然后把答案累加到
这样复杂度是的,大概是

四、持续更新中....

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注