min25筛

$min25$筛又双叒叕忘了！重新学一遍。

https://blog.csdn.net/qq_39972971/article/details/81543972

我们要求$\sum\limits_{i=1}^{n}f_i$，其中$\sum\limits_{i=1}^nf_i[isprime_i]$可以由$\sum\limits_{i=1}^ni^k[isprime_i]$简单表示。

考虑类似埃筛的过程。

我们令$F(n, i)=\sum\limits_{j=1}^nf_j[min_j \geq prime_i]$

那么我们要求的就是$F(n,1)+f_1$

$F(n, i)$怎么算？当$prime_i>n$时，$F(n,i)=0$。

否则，先考虑其中质数的贡献：$\sum\limits_{j=1}^nf_i[isprime_j]-\sum\limits_{j=1}^{i-1}f_{prime_j}$

然后考虑合数的贡献。暴力枚举$min_j$和他是$min_j$的几次方：

$\sum\limits_{j=i}^{prime_j^2 \leq n}\sum\limits_{k=1}^{prime_j^{k+1}\leq n}F( \lfloor \frac{n}{prime_j^k} \rfloor , j+1) * f_{prime_j ^ k} + f_{prime_j^{k+1}}$

这个柿子看起来非常复杂，其实非常显然（那我为啥还忘了）。

综上，$prime_j \leq i$时，$F(n,i)=\sum\limits_{j=1}^nf_i[isprime_j]-\sum\limits_{j=1}^{i-1}f_{prime_j} +\sum\limits_{j=i}^{prime_j^2 \leq n}\sum\limits_{k=1}^{prime_j^{k+1}\leq n}F( \lfloor \frac{n}{prime_j^k} \rfloor , j+1) * f_{prime_j ^ k} + f_{prime_j^{k+1}}$

注意我们