LightOJ 1038 Race to 1 Again：概率 DP 期望步數

題目描述

從 N 開始，每步隨機選一個因子 d (1 ≤ d ≤ D)，替換 D ← D/d，直到變為 1。求期望步數。N ≤ 1e5，多測試用例。

DP 遞推推導

設 E[x] 為從 x 到 1 的期望步數。x 有 k 個因子 d1..dk。
E[x] = 1 + (1/k) * Σ E[x/di]。
移項得：E[x] = (k + Σ E[x/di]) / (k - 1)（注意 di=1 時 x/di = x，移到左邊合併）。

預計算所有 E[x]

• E[1] = 0。
• 從 2 到 MAXN 遞推：枚舉因子（O(√x)），累加 E[factor]，套用公式。
• 查詢 O(1)。

C++ 代碼實現

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

const int MAXN = 100005;
double E[MAXN];

void precompute() {
    E[1] = 0;
    for (int i = 2; i < MAXN; ++i) {
        int cnt = 0;
        double sum = 0;
        for (int j = 1; j * j <= i; ++j) {
            if (i % j == 0) {
                ++cnt; sum += E[j];
                if (j * j != i) { ++cnt; sum += E[i/j]; }
            }
        }
        E[i] = (sum + cnt) / (cnt - 1); // 公式
    }
}

int main() {
    precompute();
    int T; scanf("%d", &T);
    for (int cs = 1; cs <= T; ++cs) {
        int n; scanf("%d", &n);
        printf("Case %d: %.6f\n", cs, E[n]);
    }
    return 0;
}

關鍵點

• 因子枚舉優化：j*j <= i，成對處理。
• 公式分母 cnt-1 排除了因子 1 導致的自我循環項。
• 雙精度足夠，輸出 %.6f。