Race to 1 Again LightOJ - 1038
题目大意
给你一个正整数$D$,每次我们选择一个$D$的因子$k$使得$D/=k$,问你将$D$变成$1$的操作次数的期望是多少
解题思路
考虑将$D$除以$k$后得到$D’=D/k$,那么$E(D)=\frac{1}{\sum_{k|D}}\times(E(D’)+1)$
那么将范围内的数筛一遍因子,按照公式转移即可,初始条件为$E[1]=0$,时间复杂度$O(n\sqrt{n}+T)$
AC代码
1 |
|
要是不努力,今天很牛逼,明天很傻逼
给你一个正整数$D$,每次我们选择一个$D$的因子$k$使得$D/=k$,问你将$D$变成$1$的操作次数的期望是多少
考虑将$D$除以$k$后得到$D’=D/k$,那么$E(D)=\frac{1}{\sum_{k|D}}\times(E(D’)+1)$
那么将范围内的数筛一遍因子,按照公式转移即可,初始条件为$E[1]=0$,时间复杂度$O(n\sqrt{n}+T)$
1 | #include <cmath> |