题目大意:

Dilu学习了一个关于整数的新东西,即任何大于1的正整数都至少可以被一个小于或等于该数的素数整除。他选择一个数字D。在每个回合中,他随机选择小于或等于D的素数。如果D可被整除,那么他将D除以素数获得新的D。否则他保持旧D。他重复这个过程,直到D变为1。求需要的移动的预期数量是多少

题解:

一道较为简单的概率题,可以使用记忆化搜索。
我们每次在小于D的素数(假设有q个)中选择一个,可以得到如下方程: (表达起来比较纠结,如果有更好的表达方法欢迎评论)

\[ F(D) = \sum _{D\ mod\ p[i] = 0} \frac{F(\frac{D}{p[i]})}{q} + \sum _{D\ mod\ p[i] \neq 0} \frac{F(D)}{q} \]


\[F(D) \times q = \sum _{D\ mod\ p[i] = 0} F(\frac{D}{p[i]}) + \sum _{D\ mod\ p[i] \neq 0} F(D) \]

设这q个素数中有z个不能整除D,则

\[F(D) \times (q-z) = \sum _{D\ mod\ p[i] = 0} F(\frac{D}{p[i]})\]

解得:

\[F(D) = \frac {\sum _{D\ mod\ p[i] = 0}\ \ \ F(\frac{D}{p[i]})}{q-z}\]

然后就可以DP或者记忆化搜索。

代码如下: