线性筛

数论 小专题

---

引用

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

正文

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

一、积性函数

函数$f$，若对于任意$gcd(x,y)=1$都有$f(x*y)=f(x)*f(y)$那么$f$为积性函数
若对于任意$x,y$都有$f(x*y)=f(x)*f(y)$那么$f$为完全积性函数

二、线性筛

$O(n)$的时间内求解某个东西（比如说线性筛质数）

三、常见积性函数

A、$\mu(n):$莫比乌斯函数（Code）

B、$\varphi(n):$欧拉函数（留坑）

C、$d(n):$约数个数（Article）

D、$\sigma(n):$约数和（留坑）

E、$f(x)=x^k(k\epsilon N)$幂函数

F、狄利克雷卷积

　　形如

$$h(d)=\sum_{d|n}f(d)g(\frac{n}{d})$$
　　若$f$和$g$都是积性函数那么$h$也是积性函数，可以线性筛
　　具体怎么筛请参见租酥雨's blog，典例参见该篇文章做题经验部分

Part 2不是积性函数也可以线性筛 ＞﹏＜

一、比如说这个

$$\sum_{d|T}[d为质数?1:0]\mu(\frac{T}{d})$$
题目来源：YY的GCD
题解：YYB博客链接

二、再看看这个

$$\sum_{d|T}[d为完全平方数]\mu({\frac{T}{d}})$$
题目来源：Hillan and the girl
Code：Ubuntu Pastebin

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

上面的一二式用暴力筛都能过，美其名曰埃氏筛法，就是从$1$到$n$枚举$d$然后把答案累加到$F[T]$中
这样复杂度是$\sum_{i=1}^{T}\frac{T}{i}$的，大概是$O(nlog(logn))$，$log(log10^7)=16$

四、持续更新中....