Race to 1 Again LightOJ

题意：有一个数字D，每次把D变为它的一个因数（变到所有因数的概率相等，可能是本身），变到1后停止。求对于某个初始的D变到1的期望步数。

x的因子有p[1],...,p[k]

那么ans[x]=1/k*(ans[p[1]]+1)+...+1/k*(ans[p[k]]+1)
=1/k*(ans[p[1]]+...+ans[p[k-1]])+1/k*ans[p[k]]+1
(k-1)/k*ans[x]=1/k*(ans[p[1]]+...+ans[p[k-1]])+1
ans[x]=1/(k-1)*(ans[p[1]]+...+ans[p[k-1]])+k/(k-1)

 1 #include<cstdio>
 2 #include<cmath>
 3 using namespace std;
 4 int k,T,n;
 5 double anss,ans[100100];
 6 int main()
 7 {
 8     int i,j,t;
 9     for(i=2;i<=100000;i++)
10     {
11         k=2;
12         anss=0;
13         for(j=2;j<sqrt(i);j++)
14         {
15             if(i%j!=0)    continue;
16             anss=anss+ans[j]+ans[i/j];
17             k+=2;
18         }
19         t=sqrt(i);
20         if(t*t==i)
21         {
22             anss+=ans[t];
23             k++;
24         }
25         ans[i]=anss/(k-1)+(double)k/(k-1);
26     }
27     scanf("%d",&T);
28     for(i=1;i<=T;i++)
29     {
30         scanf("%d",&n);
31         printf("Case %d: %.9f
",i,ans[n]);
32     }
33     return 0;
34 }