UOJ188口胡

本文主要是介绍UOJ188口胡，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

我们先枚举一个最大质因子，然后设 \(dp[n][k]\) 为 \(n\) 以内使用了 \(pri[k]\) 以内的质数的数的最大质因子之和，答案就是：

\[\sum_{k\leq n}dp[\lfloor\frac{n}{pri[k]}\rfloor][k-1] \]

当 \(pri[k]\) 大于 \(\sqrt{n}\) 时，后面相当于变成 \(\sqrt{n}\) 以内所有数的最大质因子之和，可以线性筛，质数个数也可以使用叶筛解决。

考虑这个 \(dp\) 怎么办。

根据上面的东西，我们设一个 \(g[n][k]\) 为 \(n\) 以内使用了 \(pri[k]\) 以内的质数的数的个数。有：

\[dp[n][k]=\sum_{i=1}^{k-1}g[\lfloor\frac{n}{pri[i]}\rfloor][i-1]\times pri[i] \]

只要一边筛 \(g\) 一边丢到 \(dp\) 数组里边就好了。

但是注意到丢进去的复杂度是 \(O(\frac{n}{\ln^2n})\) 的，考虑优化。。。

这个 \(g\) 是十分经典的叶筛。\(g\) 的定义为仅用过 \([1,pri[k]]\) 的质数，叶筛的 \(f\) 定义为 \([1,pri[k]]\) 的的质数都没被使用过，即最小质因子为 \(pri[k]\)。

转移可以参考这个过程。得到有：

\[g[n][k]=g[n][k-1]+g[\frac{n}{pri[k]}][k] \]

注意到其实增加的这一部分（\(g[\frac{n}{pri[k]}][k]\)）其实就是不大于 \(n\) 的最大质因子为 \(pri[k]\) 的数的数量。

直接顶上去代替 \(dp\) 不就好了。

转移的话可以使用叶筛的那种转移，滚动数组就好了（）

实际上，对于一个 \(g[n][k]\)，有用的状态数量只有 \(O(\frac{n^{\frac{3}{4}}}{\ln n})\) 个，可以直接进行区间加什么的。

复杂度 \(O(\frac{n^{\frac{3}{4}}}{\ln n})\)。

这篇关于UOJ188口胡的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！