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

时间：2022-04-10 07:48:02

数学期望/马尔可夫过程

　　DP/记忆化搜索

　　刘汝佳老师白书上的例题……

 //UVA 11762

 #include<vector>

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<iostream>

 #include<algorithm>

 #define rep(i,n) for(int i=0;i<n;++i)

 #define F(i,j,n) for(int i=j;i<=n;++i)

 #define D(i,j,n) for(int i=j;i>=n;--i)

 using namespace std;

 int getint(){

     int v=,sign=; char ch=getchar();

     while(ch<''||ch>''){ if (ch=='-') sign=-; ch=getchar();}

     while(ch>=''&&ch<=''){ v=v*+ch-''; ch=getchar();}

     return v*=sign;

 }

 const int N=1e6+;

 #define debug

 /******************tamplate*********************/

 int prime[N],tot;

 bool check[N];

 void getpr(int n){

     memset(check,,sizeof check);

     F(i,,n){

         if (!check[i]) prime[tot++]=i;

         rep(j,tot){

             if (i*prime[j]>n)break;

             check[i*prime[j]]=;

         }

     }

 }

 bool vis[N];

 double f[N];

 double dp(int x){

     if (x==) return 0.0;

     if (vis[x]) return f[x];

     vis[x]=;

     double &ans = f[x];

     int g=,p=; ans=;

     rep(j,tot){

         if (prime[j]>x) break;

         p++;

         if (x%prime[j]==){ g++; ans+=dp(x/prime[j]);}

     }

     ans=(ans+p)/g;

     return ans;

 }

 int main(){

 #ifndef ONLINE_JUDGE

     freopen("11762Race_to_1.in","r",stdin);

     freopen("11762Race_to_1.out","w",stdout);

 #endif

     getpr(N-);

     int T=getint();

     F(t,,T)

         printf("Case %d: %.10lf\n",t,dp(getint()));

     return ;

 }

相关文章