uva 11762 - Race to 1(马尔可夫)

题目链接：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 <cstdio>
#include <cstring>
#include <algorithm>

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;
}