NMD我怎么现在才会这沙雕玩意儿.jpg
感觉挺简单的，主要是适用范围比较小，大概能筛某些性质比较奇妙的上界在 $10^{13}$ ~ $10^{14}$的积性函数
首先介绍 $\text{Powerful}$ $\text{Number}$ 是啥，当一个数满足其所有质因数的指数都大于 $1$ 的时候我们称其为 $\text{Powerful}$ $\text{Number}$ ，下面简单说明其重要性质： $n$ 以内的 $\text{Powerful}$ $\text{Number}$ 的数量为 $\sqrt n$ 级别的，首先发现每个 $\text{Powerful}$ $\text{Number}$ 都能表示成 $x^2y^3$ 的形式
也就是说，如果我们的计算复杂度只跟 $\text{Powerful}$ $\text{Number}$ 有较大关系，那么大概能非常快的算出答案
假设现在要筛出积性函数 $F(x)$ 的前缀和，且我们能找到一个函数 $G(x)$ 满足 $G\not=F,G(\text{prime})=F(\text{prime})$ ，那么对于函数 $H=\frac FG$ ，其大概也是一个积性函数，且素数带入结果均为 $0$ ，这样可以推出来一个结论： $H$ 函数只有 $\text{Powerful}$ $\text{Number}$ 带入的时候值可能不为 $0$ ，那么我们暴力搜出来 $H$ 不为 $0$ 的代入值，然后求 $\sqrt n$ 次 $G$ 的前缀和即可，关于怎么构造 $G$ 和计算其前缀和就各凭本事了，关于 $H$ 有一个我自己 $yy$ 的垃圾方法，就是由于 $H$ 为积性函数，因此我们暴力递推出所有素数幂的 $H$ 值最后爆搜的时候乘一乘，关键点在于对于每一个素数其幂的递推关系可以用分治 $ntt$ /多项式求逆优化（不过一共貌似只有 $\log n$ 项多半跑不过 $k^2$ 递推，因此最好的办法还是递推出来打表观察规律）
如果找不到规律， $H$ 的预处理复杂度是 $O(n\log n\times \text{calc(G)})$ ，爆搜+计算的复杂度是 $O(\sqrt n\times \text{calc}(G_{presum}))$ 把计算 $G$ 前缀和的复杂度跟这些分开算，或者跟枚举出的 $\text{Powerful}$ $\text{Number}$ 有关可以跟前面一个套起来积分算复杂度