题目链接：uva 11762 - Race to 1

题目大意：给出一个整数N，每次可以在不超过N的素数中随机选择一个P，如果P是N的约数，则把N变成N/P，否则N不变。问平均情况下需要多少次选择，才能把N变成1.

解题思路：马尔可夫，例如N=6时，f(6)=1+f(6)?13+f(4)?13+f(2)?13，1是只第一次转移，后面分别对应的是选择5，2，3的情况.所以有f(x)=∑f(x/y)+p(x)g(x),p(x)为不超过x的素数个数，g(x)为是x因子的素数个数。

#include 
   
     #include 
    
      #include 
     
       using namespace std; const int maxn = 1e6; int np, prime[maxn+5], vis[maxn+5]; double dp[maxn]; void prime_table(int n) { np = 0; memset(vis, 0, sizeof(vis)); for (int i = 2; i <= maxn; i++) { if (vis[i]) continue; prime[np++] = i; for (int j = i * 2; j <= maxn; j += i) vis[j] = 1; } } double dfs (int n) { if (vis[n]) return dp[n]; if (n == 1) return dp[n] = 0; double& ans = dp[n]; int g = 0, p = 0; ans = 0; for (int i = 0; i < np && prime[i] <= n; i++) { p++; if (n % prime[i] == 0) { g++; ans += dfs(n / prime[i]); } } return ans = (ans + p) / g; } int main () { prime_table(maxn); memset(vis, 0, sizeof(vis)); int cas, n; scanf("%d", &cas); for (int kcas = 1; kcas <= cas; kcas++) { scanf("%d", &n); printf("Case %d: %.10lf\n", kcas, dfs(n)); } return 0; }