您也可以阅读体验更好、叙述更严谨的论文。
杜教筛是一种可以用低于线性的复杂度计算出积性函数前缀和的神奇算法。
在开始前，请您先阅读有关积性函数和莫比乌斯反演的文章，确保您已经理解了。
继续阅读“杜教筛”
积性函数和莫比乌斯反演
您也可以阅读体验更好、叙述更严谨的论文。
积性函数
数论函数是指定义域在正整数、而值域在复数域上的一类函数，即\(f:\mathbb{Z}^{+}\rightarrow\mathbb{C}\)。
下文中的数论函数值域都在整数上。积性函数是一种特殊的数论函数，他们满足对于任意互质的一对数\(p,q\)，有\(f(p)\cdot f(q)=f(pq)\)，即他们的函数值乘起来等于他们乘起来的函数值。特别地，如果对于任意不互质两数上面的条件也成立，则称这个函数为完全积性函数。