杜教筛小结

杜教筛是用来解决这样一个问题的:给定一个积性函数f(x)f(x),求i=1nf(i)\sum_{i=1}^nf(i)

具体是这样: 找到两个积性函数g,sg,s,使得gf=sg* f=s,并且可以快速算出g和s的前缀和.

|

博客使用Disqus作为评论系统