https://vjudge.net/contest/182687#problem/C
题意： 给出一个数字Ｄ 我们可以选择１－Ｄ中可以被Ｄ整除的数字，然后用Ｄ出得到一个新的数字Ｄ１； 然后在找所有Ｄ１的因子，用Ｄ１除，直到得到１； 问除的次数的期望值；
思路： d[i] 代表从ｉ除到０的期望步数；那么假设ｉ一共有ｃ个因子（包括１和本身） d[i] = ( d[1] + d[a2] + d[a3] + d[a4] ….. + d[i] + c) / c; (加c是因为每一个期望值都会加1,因为多出一步才变成它) 把右边的d[i]移到左边就是； ( (c - 1) / c ) * d[i] = ( d[1] + d[a2] + d[a3] + d[a4] ….. + d[ac- 1] + c) / c; 那么d[i]就等于所有因子的期望和（除掉ｉ）加上ｃ再除以ｃ-１；
#include <iostream> #include <cstdio> using namespace std; const int maxn=100005; double dp[100005]; void init() { for(int i=2; i<maxn; i++) { int c=0; double sum=0; for(int j=1; j*j<=i; j++) { if(i%j==0) { c++; sum+=dp[j]; if(i/j!=j) { c++; sum+=dp[i/j]; } } } dp[i]=(sum+c)/(c-1); } } int main() { int t; init(); int ca=1; scanf("%d",&t); while(t--) { int n; scanf("%d",&n); printf("Case %d: %.8f\n",ca++,dp[n]); } return 0; }