Uva11762 Race to 1——有向无环图&&记忆化搜索

题意

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

分析

本题可以画出一个状态转移图，

例如 $n=6$ 时，

$n$ 的每个约数都对应一个状态，每个状态转移都有一定概率，从每个状态出发转移的概率和为1.

设 $f(i)$ 表示当前的数为 $i$ 时接下来需要选择的期望次数，可列出方程：

$$f(6) = 1 + f(6)/3 + f(3)/3 + f(2)/3$$

一般地，设不超过 $x$ 的素数有 $p(x)$ 个，其中有 $g(x)$ 个是 $x$ 的因子，则

$$f(x) = 1 + f(x) imes [1 - frac{g(x)}{p(x)}] + sum_{x | y} frac{f(x/y)}{p(x)}$$

即

$$f(x) = frac{sum _{x|y}f(x/y) + p(x)}{g(x)}$$

边界为 $f(1)=0$，因为 $x/y < x$（即形成的是有向无环图），可以用记忆化搜索的方式 计算 $f(x)$，否则就要用高斯消元了。

#include<bits/stdc++.h>
using  namespace std;

//返回n以内素数的个数
//埃氏筛法O(nloglogn)
const int maxn = 1000000 + 10;
int prime[maxn];            //prime[i]表示第i个素数
bool is_prime[maxn + 1];    //is_prime[i]为true表示i是素数
int prime_cnt;

int sieve(int n)
{
    int cnt = 0;
    for (int i = 0; i <= n; i++)  is_prime[i] = true;
    is_prime[0] = is_prime[1] = false;
    for (long long i = 2; i <= n; i++)
    {
        if (is_prime[i])
        {
            prime[cnt++] = i;
            for (long long j = i * i; j <= n; j += i)  is_prime[j] = false;  //i * i可能爆int
        }
    }
    return cnt;
}

bool vis[maxn];
double f[maxn];
double dp(int x)
{
    //printf("x: %d
", x);
    if(vis[x])  return f[x];
    if(x == 1)  return 0.0;
    vis[x] = 1;
    double& ans = f[x];
    int g = 0, p = 0;    //累加g[x] 和 p[x]
    ans = 0;
    for(int i = 0;i <prime_cnt && prime[i] <= x; i++)
    {
        p++;
        if(x % prime[i] == 0)
        {
            g++;
            ans += dp(x / prime[i]);
        }
    }
    ans = (ans + p) / g;
    return ans;
}

int n;

int main()
{
    prime_cnt = sieve(1000000);

    int T, kase = 0;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d", &n);
        printf("Case %d: %.8f
", ++kase, dp(n));
    }
    return 0;
}