UVA 11762 Race To 1 [期望DP]

　　给一个数N，每步随机选一个不大于N的质数X，若X整除N，则N=N/X，否则N不变。求N变为1的期望步数。

　　常规的期望DP，先预处理不大于N的质数个数以及N的质因数，d[n]=p0*d[n]+p1*d[n/d1]+p1*d[n/d2]...+1，其中d1,d2..是n的质因数，p0为选中一个质数不为n的质因数的概率，移项即可得到d[n]的表达式。

 1 #include <string.h>
 2 #include <stdio.h>
 3 #include <vector>
 4 #define MAXN 1000005
 5 using namespace std;
 6 int cas, n;
 7 int pri[MAXN], totp[MAXN];
 8 double d[MAXN];
 9 vector<int> vec[MAXN];
10 void init(){
11     pri[1] = 1;
12     for (int i = 2; i < MAXN; i++) if (!pri[i]){
13         vec[i].push_back(i);
14         for (int j = i*2; j < MAXN; j += i)
15             pri[j] = 1, vec[j].push_back(i);
16     }
17     for (int i = 1; i < MAXN; i++)
18         totp[i] = totp[i-1] + (pri[i]==0);
19     memset(d, 0, sizeof d);
20 }
21 double dp(int n) {
22     if (n == 1) return 0;
23     if (d[n] != 0) return d[n];
24     double tt = 0;
25     for (int i = 0; i < vec[n].size(); i++)
26         tt += dp(n/vec[n][i])/totp[n];
27     return d[n] = (tt + 1) / (vec[n].size()*1.0/totp[n]);
28 }
29 int main(){
30     //freopen("test.in","r",stdin);
31     scanf("%d", &cas);
32     init();
33     for (int ca = 1; ca <= cas; ca++) {
34         scanf("%d", &n);
35         printf("Case %d: %.10f\n", ca, dp(n));
36     }
37     return 0;
38 }