UVA 11762 Race to 1：記憶化遞歸計算期望步數

UVA 11762 Race to 1：記憶化搜尋

題目大意

從 x 開始，每步隨機選一個質因數 p（均勻），將 x 替換為 x/p。求期望步數 f(x) 直到變為 1。

遞推公式

設 x 的質因數有 g 個（含重複），總質因數個數 p（不含重複？不，題目為所有質因數含重複）。實際推導：

f(1) = 0
f(x) = 1 + (1/p) * Σ f(x / prime_i)   // prime_i 為 x 的所有質因數（含重複）
→ f(x) = (p + Σ f(x/prime_i)) / g    // g 為能整除 x 的質因數個數（含重複）

記憶化搜尋實作

const int MAXN = 1000005;
int primes[MAXN], prime_cnt;
bool vis[MAXN];
double f[MAXN], v[MAXN];

void sieve() {
    for (int i=2;i*i