动态规划晋级——Race to 1 Again【概率DP】
转载请注明出处：http://blog.csdn.net/a1dark
分析：
题意：给一个数，用这个数的约数(包括自己)去除这个数，直到得数为1，求除的次数的期望。
思路：设一个数的约数有num个，E[n] = E[a[1]]/num+E[a[2]]/num+...+E[a[num]]/num+1 (因为又除一次，所以+1)
整理得：E[n]=(E[a[1]]+E[a[2]]+...+E[a[num-1]]+num)/(num-1)
#include<stdio.h>#include<cmath>const int N=100010;double dp[N];void Init (){dp[1]=0;for (__int64 i=2;i<N;i++){double sum=0;int cnt=0;for (__int64 j=1;j*j<=i;j++)//这里必须要优化、否则会超时if (i%j==0){sum+=dp[j];cnt++;if(j*j!=i){ sum+=dp[i/j]; cnt++;}}sum+=cnt;dp[i]=sum/(cnt-1);}}int main (){int T,n;scanf("%d",&T);Init ();for (int Cas=1;Cas<=T;Cas++){scanf("%d",&n);printf("Case %d: %lf\n",Cas,dp[n]);}return 0;}