题意：
给一个数n， 每次从小于等于n的素数里选一个P， 如果能被n整除， 那么就n就变成n / P。
问： n 变成1的期望。
思路：
设小于等于n的素数有p 个， 其中是n的约数的有g个。
则E[x] = 1 + 1/p * (1 - g/p) + sigma(i = 0, 1, 2, g)num[i] * 1/p。
化简得：
E[x] = (p + sigma(i = 0, 1, 2, g)num[i]) / g。
代码如下：
#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 1000010
#define MOD 1000000007
#define eps 1e-6
int prime_size;
int prime_[MAXN];
double f[MAXN];
bool prime[MAXN], vis[MAXN];
int n;
bool is_prime(int x)
{
if(x <= ) return false;
for(int i = ; i * i <= x; i ++)
if(x % i == ) return false;
return true;
}
void p_init()
{
memset(vis, false, sizeof(vis));
prime_size = ;
for(int i = ; i < MAXN; i ++)
if(is_prime(i))
{
prime_[prime_size ++] = i;
for(int j = ; j * i < MAXN; j ++)
prime[j * i] = true;
}
f[] = f[] = ;
}
double dp(int x)
{
if(x == ) return 0.0;
if(vis[x]) return f[x];
vis[x] = true;
int g = ;
int p = ;
double& ans = f[x];
ans = ;
for(int i = ; i < prime_size && prime_[i] <= x; i ++)
{
p ++;
if(x % prime_[i] == )
{
g ++;
ans += dp(x / prime_[i]);
}
}
ans = (ans + p) / g;
return ans;
} int main()
{
int T;
int kcase = ;
p_init();
scanf("%d", &T);
while(T --)
{
scanf("%d", &n);
printf("Case %d: %.7lf\n", ++ kcase, dp(n));
}
return ;
}