UOJ 分析 题目要求的就是 $[l,r]$ 中的数的次大质因子的和，这里的次大是可重集的次大。 首先对其差分，变为求 $[1, n]$ 中的数的次大质因子之和。 这个数据范围启发我们考虑一些筛法，仔细思考之后发现只能考虑 Min_25 筛。 然而直接做显然是不行的。我们需要对其第二部分即求答案的部分进行一些改造，使得它能求出我们想求的东西。 对于一个合数，我们在其剩余的质因子个数 $\le...
LOJ 分析 可以发现答案即为 数论分块计算即可。 再考虑 $\sum \sigma_0\!^2(i)$。我们知道 $\sigma_0\!^2$ 是积性函数，且有 $\sigma_0\!^2(p) = 4$、$\sigma_0\!^2(p ^ k) = (k + 1) ^ 2$，因此可以使用 Min_25 筛计算。 代码 // ===============================...
LOJ 分析 注意到 不妨假装 $f(2)=1$，于是就可以 Min_25 筛了。 考虑到在 Min_25 筛的第二步即求 $S(n,j)$ 时，如果 $j=1$ 则质数部分算了 $2$ 的贡献，直接加上 $2$ 即可。 代码 // =================================== // author: M_sea // website: http://m-s...
设 $f$ 为积性函数，且其在质数处的取值 $f(p)$ 是关于 $p$ 的多项式，且其在质数的幂的取值 $f(p^c)$ 能快速计算，则 Min_25 筛可以在 $\mathcal{O}(\frac{n^{\frac{3}{4}}}{\log n})$ 的时间复杂度内算出 $\sum_{i=1}^nf(i)$。 思路 为了方便，设 $\mathrm{P}$ 为质数集，$p_i$ 为第 $...