Min_25筛

赞美$Min25$!

赞美

$Min25$筛用于求积性函数前缀和，适用与$n\leq 10^{11}$

后面如果只求质数部分的共享，满足第一项即可。

定义$minp(i)$为$i$的最小素因子。

由于$f(p)$为多项式，$\sum_{k}a_k\sum[i\in P]i^k$,需要分开来算！

先假装所有数都是质数满足$f(p)$，思想就是减去不合法的部分。

设

$g(n,j)=\sum_{i=1}^n[i\in Prime\ or \ min(i)>p_j]i^k$

考虑转移

${p_j}^2>n$,显然我放宽第二个条件没有任何变化。
${p_j}^2\leq n$,需要减去$\sum_{i=1}^n[min(i)=p_j]i^k\rightarrow p_j^k\sum_{i=1}^{n/p_j}[min(i)>p_{j-1}]i^k=(g(\frac{n}{p_j},j-1)$，但是重复计算了$\sum_{i=1}^{j-1}p_i^k)$

整合之后即。

$g(n,j)=\begin{cases} g(n,j-1)&{p_j}^2\gt n\\ g(n,j-1)-p_j^k(g(\frac{n}{p_j},j-1)-\sum_{i=1}^{j-1}p_i^k)&{p_j}^2\le n\end{cases}$

边界问题$g(n,0)=\sum_{i=2}^n i^k$

$\frac{n}{i}$只有$\sqrt{n}$种，$j$可以滚动数组，空间复杂度$\sqrt n$,时间复杂度$\sqrt{n}\times \frac{\sqrt{n}}{\log n}$，但由于第一个条件的存在复杂度$\frac{n^{0.75}}{\log n}$ ，不会算。

设

$S(n,j)=\sum_{i=1}^n[min(i)>p_j]f(i)$

$p_j\geq n ,S(n,j)=0$
质数部分 $g(n,|P|)-\sum_{i=1}^{j-1}f(p_i)$
合数部分枚举最小因子，以及最小因子在其中占的数量，因为这样根据积性函数就可以把其分解出来$f(p_k^e)$,剩余部分就是$S(\frac{n}{p_k^e},k)$,注意$e\geq 2$，是还要加上本身。
注意在枚举质数时，同样保证$p_i^2\leq n$。根据性质一即可推出。

$S(n,j)=g(n,|P|)-\sum_{i=1}^{j-1}f(p_i)+\sum_{k> j}\sum_{e}(f(p_ke)(S(\frac{n}{p_k^e},k)+(e!=1))$

$\frac{n}{i}$只有$\sqrt{n}$种，使用递归处理，神仙说不需要记忆化。时间复杂度$\frac{n^{0.75}}{\log n}$。