Java教程

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口胡的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!