1 //Accepted    2860 KB    16 ms 2 //概率 3 //对于n，假设n变成1的期望步数为p(n) 4 //则p(n)=1/t*sum((1+p(d))) d|n 5 //解得：p(n)=1/(t-1)*(t+sum(p(d))) d|n d!=n; 6 //下面我们可以改造筛素数的方法，对于每个d，看他整除那些数 7 #include <cstdio> 8 #include <cstring> 9 #include <iostream>10 #include <queue>11 #include <cmath>12 #include <algorithm>13 using namespace std;14 /**15   * This is a documentation comment block16   * 如果有一天你坚持不下去了，就想想你为什么走到这儿！17   * @authr songt18   */19 const int imax_n = 100005;20 double f[imax_n];21 int t[imax_n];22 void pre()23 {24     for (int i=0;i<imax_n;i++)25     {26         f[i]=1;27         t[i]=1;28     }29     f[1]=0;30     for (int i=2;i<imax_n-4;i++)31     {32         f[i]=(f[i]+1)/t[i];33         for (int j=2*i;j<imax_n-4;j+=i)34         {35             f[j]+=1+f[i];36             t[j]++;37         }38     }39 }40 int n;41 int main()42 {43     pre();44     int T;45     int t=0;46     scanf("%d",&T);47     while (T--)48     {49         scanf("%d",&n);50         printf("Case %d: %.6lf\n",++t,f[n]);51     }52     return 0;53 }