题意：
给一个数n， 每次操作是随机的选择一个[1,N]区间内能够被n整除的数进行除法， 然后得到一个新的n。
问n变成1时的期望操作次数。
思路：
设E[n] 为 当数为x时， 变成 1 期望的次数， 则有转移方程。
E[n] = sigma E[n / x[i]] / k + 1（x[i] 为能被n被整除的数）， k为n在区间[1,n]能被n整除的个数。
化简：E[n] = E[n] / k + sigma E[n / x[i]] / k + 1
= k * (sigmaE[n / x[i]] / k + 1) / (k - 1)
= (sigmaE[n / x[i]] + k) / (k - 1)。
代码：
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <set>
#include <map>
#include <list>
#include <queue>
#include <string>
#include <vector>
#include <fstream>
#include <iterator>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long
#define MAXN 100010
#define MOD 1000000007
#define eps 1e-6
int n;
double f[MAXN];
bool vis[MAXN];
vector <int> g[MAXN];
void init()
{
for(int i = ; i < MAXN; i ++)
for(int j = ; j * i < MAXN; j ++)
g[j * i].push_back(i); f[] = ;
memset(vis, false, sizeof(vis));
}
double dp(int x)
{
if(x == ) return 0.0;
if(vis[x]) return f[x];
vis[x] = true;
double& ans = f[x];
ans = 0.0;
for(int i = ; i < g[x].size(); i ++)
ans += dp(x/g[x][i]);
ans += (g[x].size() + 1.0);
ans /= g[x].size();
return ans;
} int main()
{
int T;
int kcase = ;
init();
scanf("%d", &T);
while(T --)
{
scanf("%d", &n);
printf("Case %d: %.7lf\n", ++ kcase, dp(n));
}
return ;
}