杜教筛

[Marcythm]

https://oi-wiki.org/math/number-theory/du/

OI Wiki 是一个编程竞赛知识整合站点，提供有趣又实用的编程竞赛知识以及其他有帮助的内容，帮助广大编程竞赛爱好者更快更深入地学习编程竞赛

[LsqAlpha]

想问下$f^2(n)$是自己卷自己吗？

[cyh-toby]

@LsqAlpha
想问下$f^2(n)$是自己卷自己吗？

你是说问题二那里吗？那个好像是指 f(n)·f(n)。

[abcdhhhh]

请问杜教筛和积性函数之间有什么联系吗？杜教筛并没有要求是积性函数吧

[qwqAutomaton]

那啥，问题一代码里面那个“路径压缩”是什么啊……

不应该是“记忆化”吗qwq

[2020gyk080]

@abcdhhhh
请问杜教筛和积性函数之间有什么联系吗？杜教筛并没有要求是积性函数吧

杜教筛就是用来求积性函数的前缀和的罢。

[liuzimingc]

原文：

无论数论函数 f 是否为积性函数，只要可以构造出恰当的数论函数 g, 便都可以考虑用杜教筛求 f 的前缀和。

[abcdhhhh]

@2020gyk080

@abcdhhhh
请问杜教筛和积性函数之间有什么联系吗？杜教筛并没有要求是积性函数吧

杜教筛就是用来求积性函数的前缀和的罢。

不一定吧，它只要求 f*g 前缀和可以快速求，并没有要求 f 是积性函数