RainAir
My OI Blog
RainAir

杜教筛
文章归档

杜教筛学习笔记

预备知识 杜教筛是一种能在比线性复杂度还优秀的复杂度中处理处积性函数的前缀和。 主要运用 Dircichlet 卷积来完成复杂度的化简。 定义 设 $ f(n) $ 为一个数论函数,$ S(n) = \Sigma_{i=1}^nf(i)$。 我们考虑再找到一个合适的数论函数 $g(i)$,使得 $$ \Sigm…

   342   2018-08-17 去围观
标签
近期评论