UVa11762 Race to 1

期望DP

一个数只能分解成不大于它的数，那么转移构成拓扑关系。

试了一下预处理出不大于x的质数个数，然而程序并没有变快

 1 /*by SilverN*/
 2 #include<algorithm>
 3 #include<iostream>
 4 #include<cstring>
 5 #include<cstdio>
 6 #include<cmath>
 7 #include<vector>
 8 using namespace std;
 9 const int mxn=1000100;
10 int read(){
11     int x=0,f=1;char ch=getchar();
12     while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
13     while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
14     return x*f;
15 }
16 double f[mxn];
17 int pri[mxn],cnt=0,sum[mxn];
18 bool vis[mxn];
19 void init(){
20     for(int i=2;i<mxn;i++){
21         if(!vis[i]){pri[++cnt]=i;sum[i]++;}
22         for(int j=1;j<=cnt && (long long)i*pri[j]<mxn;j++){
23             vis[i*pri[j]]=1;
24             if(i%pri[j]==0)break;
25         }
26     }
27 //    for(int i=2;i<mxn;i++){sum[i]+=sum[i-1];};
28     return;
29 }
30 double DFS(int x){
31     if(x==1)return 0;
32     if(f[x])return f[x];
33     double res=0;int c=0;
34     int n=0;
35     for(int i=1;i<=cnt && pri[i]<=x;i++){
36         n++;
37         if(x%pri[i]==0){
38             c++;
39             res+=DFS(x/pri[i]);
40         }
41     }
42 //    res=(res+sum[x])/(double)c;
43     res=(res+n)/(double)c;
44     return f[x]=res;
45 }
46 int main(){
47     int i,j,x;
48     int T=read(),cas=0;
49     init();
50     while(T--){
51         x=read();
52         printf("Case %d: %.10f
",++cas,DFS(x));
53     }
54     return 0;
55 }