回杭州的路上胡的。
其实是模拟赛考了一个积性函数前缀和，然后我由于生病没打，所以只胡了，然后由于不想整洲阁筛，所以胡了一个筛子。
应该比较简单，适用范围也较小，大致能搞 DIVCNTK 这种满足 \(f(p)=C\) （常数）且 \(f(p^a)\) 可以快速求的，不过复杂度不是很优，常数也不小。
之前我只会 \(O(Cn^{2/3})\) 的块筛，后来发现稍作改动即可做到 \(O(n^{2/3}\log C)\)。
优点在于难度很小。仅涉及到 PN 筛和快速幂的倍增。不过由于比较简单，相信大家自己以前也发明过。
我们构造 \(h_C=1 * 1 * 1 * \dots * 1\)（\(C\) 个恒等函数 \(1\)，$* $ 表示狄利克雷卷积），容易发现 \(h_C(p)=f(p)=C\)。
使用 PN 筛，
\[\sum_{i=1}^nf(i)=\sum_{j\textrm{ is PN}}(f/h_C)(j)\sum_{k=1}^{\lfloor\frac nj\rfloor}h_C(k) \]线筛预处理出 \(n^{2/3}\) 以内的部分，我们只用得到 \(h_C\) 的块筛即可做到在 \(O(n^{2/3})\) 内获得 \(f\) 的块筛。
当 \(C\le1\) 时，\(h_C\) 的块筛是平凡的。
当 \(2\nmid C\) 时，由于 \(h_C=h_{C-1}* 1\)，故
\[\sum_{i=1}^nh_C(i)=\sum_{i=1}^{n}h_{C-1}(i)\left\lfloor\frac ni\right\rfloor \]当 \(2|C\) 时，由于 \(h_C=h_{C/2}* h_{C/2}\)，故
\[\sum_{i=1}^nh_C(i)=\sum_{i=1}^{n}h_{C/2}(i)\sum_{j=1}^{\left\lfloor\frac ni\right\rfloor}h_{C/2}(j) \]对 \(n^{2/3}\) 以内进行线筛，更高部分进行数论分块，即可做到单行转移 \(O(n^{2/3})\)。
由于中途一共会经过 \(O(\log C)\) 层，总复杂度 \(O(n^{2/3}\log C)\)。
标签：lfloor,飞机,筛子,frac,log,sum,rfloor,误点,PN From： https://www.cnblogs.com/myee/p/sieve-back-Hangzhou.html