【UVA】【11762】Race to 1（得到1）

数学期望/马尔可夫过程

　　DP/记忆化搜索
　　刘汝佳老师白书上的例题……
 1 //UVA 11762
 2 #include<vector>
 3 #include<cstdio>
 4 #include<cstring>
 5 #include<cstdlib>
 6 #include<iostream>
 7 #include<algorithm>
 8 #define rep(i,n) for(int i=0;i<n;++i)
 9 #define F(i,j,n) for(int i=j;i<=n;++i)
10 #define D(i,j,n) for(int i=j;i>=n;--i)
11 using namespace std;
12 int getint(){
13     int v=0,sign=1; char ch=getchar();
14     while(ch<'0'||ch>'9'){ if (ch=='-') sign=-1; ch=getchar();}
15     while(ch>='0'&&ch<='9'){ v=v*10+ch-'0'; ch=getchar();}
16     return v*=sign;
17 }
18 const int N=1e6+10;
19 #define debug
20 /******************tamplate*********************/
21 int prime[N],tot;
22 bool check[N];
23 
24 void getpr(int n){
25     memset(check,0,sizeof check);
26     F(i,2,n){
27         if (!check[i]) prime[tot++]=i;
28         rep(j,tot){
29             if (i*prime[j]>n)break;
30             check[i*prime[j]]=1;
31         }
32     }
33 }
34 bool vis[N];
35 double f[N];
36 double dp(int x){
37     if (x==1) return 0.0;
38     if (vis[x]) return f[x];
39     vis[x]=1;
40     double &ans = f[x];
41     int g=0,p=0; ans=0;
42     rep(j,tot){
43         if (prime[j]>x) break;
44         p++;
45         if (x%prime[j]==0){ g++; ans+=dp(x/prime[j]);}
46     }
47     ans=(ans+p)/g;
48     return ans;
49 }
50 int main(){
51 #ifndef ONLINE_JUDGE
52     freopen("11762Race_to_1.in","r",stdin);
53     freopen("11762Race_to_1.out","w",stdout);
54 #endif
55     getpr(N-2);
56     int T=getint();
57     F(t,1,T)
58         printf("Case %d: %.10lf
",t,dp(getint()));
59     return 0;
60 }
View Code