LightOJ 1038 Race to 1 Again（概率dp+期望）

题意：
给出一个数n，每次选择n的一个约数m，n=n/m，直到n=1，求次数的期望。

思路：
d【i】表示将i这个数变成1的次数期望。

现在对于D来说，d【D】=1/cnt*{（d【D/1】+1）+（d【D/x1】+1）+（d【D/x2】+1）....+（D【D/D】+1）}

化简得 d【D】=1/（cnt-1）*（d【D/1】+d【D/x1】+...d【D/D】+cnt）

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<cstdio>
 5 #include<sstream>
 6 #include<vector>
 7 #include<stack>
 8 #include<queue>
 9 #include<cmath>
10 #include<map>
11 #include<set>
12 using namespace std;
13 typedef long long ll;
14 typedef pair<int,int> pll;
15 const int INF = 0x3f3f3f3f;
16 const int maxn = 1e5 + 5;
17 
18 int n;
19 double d[maxn];
20 
21 void init()
22 {
23     d[1]=0;
24     for(int i=2;i<=1e5;i++)
25     {
26         d[i]=0;
27         int cnt=0;
28         for(int j=1;j*j<=i;j++)
29         {
30             if(i%j==0)
31             {
32                 if(i/j!=j)
33                 {
34                     cnt+=2;
35                     d[i]+=d[j]+d[i/j]+2;
36                 }
37                 else
38                 {
39                     cnt+=1;
40                     d[i]+=d[j]+1;
41                 }
42             }
43         }
44         d[i]/=(1.0*(cnt-1));
45     }
46 }
47 
48 int main()
49 {
50     //freopen("in.txt","r",stdin);
51     int T;
52     int kase=0;
53     scanf("%d",&T);
54     init();
55     while(T--)
56     {
57         scanf("%d",&n);
58         printf("Case %d: %.7f
",++kase,d[n]);
59     }
60     return 0;
61 }