不会还有人做 牵连的世界 推式子吧

· · 题解

以防有人不知道 P9157 提出的技巧。搬运过来。

警惕筛子入侵莫反题。

求

\sum_{i=1}^n \sum_{j=1}^ m f(ij)

其中 f 是素数幂可以快速求出的积性函数。

巨大粗暴的想法是只要能快速求 F(n,x)=\sum_{i=1}^x f(ni) 然后求 \sum_{i=1}^n F(i,m) 就可以了！

考虑逐个去除 n 的质因数的贡献，最后 n=1 的时候直接预处理前缀和就行。取 n 的质因数 p 和其指数 c，枚举 1\dots x 中 p 上面的指数，可以发现

F(n,x)=\sum_{i\ge 0} f(p^{i+c})( F(n/p^c,\lfloor x/p^c\rfloor )-F(n/p^{c-1},\lfloor x/p^{c+1}\rfloor))

取 p 为 n 最大的质因数，直接记忆化递归计算。加上预处理 nx 较小的 f 之后，跑 5\times 10^5 大约需要 700ms。可以通过本题 5\times 10^5 的测试点。

一份不算很好的实现