hjm0703's blog

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub. Qu...

引入首先这个算法是为了解决求解积性函数求前缀和：$\sum_{i=1}^n f(i)$ 解决的。 其有两个前提： 所有的 $f(p)$ 必须能否被表达为一个类似 $a+bp+cp^2 \dots$。 所有的 $f(p^e)$ 在知道 $p,e,p^e$ 的情况下能够快速求出 $f$。 其算法的大致思路就是分成 质数 和 合数 分别解决，如下： $$\sum_{i=1}...