UVa 11762 - Race to 1

      #include<iostream>

#include<cstdio>

#include<string>

#include<cstring>

#include<cmath>

#include<set>

#include<map>

#include<stack>

#include<vector>

#include<algorithm>

#include<queue>



#define ull unsigned long long

#define ll long long

#define lint long long

using namespace std;



const double eps=1e-12;

const int INF=0x3f3f3f3f;

const int N=1000010;

double dp[N];//记忆化搜索数组

int p[N];//标记是否是素数

int prime[N];//将素数从小到大放到prime数组里面

double dfs(int x)

{

    if(dp[x]>=-0.5)

    return dp[x];//记忆化

    if(x==1)//边界

    return (dp[x]=0.0);

    double sum=0.0;

    int p=0,g=0;//p表示所有小于等于x的素数个数 g表示这些素数中是x的约数的个数

    for(p=0;prime[p]<=x;++p)//枚举所以小于等于x的素数

    if(x%prime[p]==0)

    {

        ++g;

        sum+=dfs(x/prime[p]);

    }

    return (dp[x]=(sum+p)/g);//这个式子推导可得

}

int main()

{

    //freopen("data.in","r",stdin);

    memset(p,-1,sizeof(p));

    int ln=0;

    for(int i=2;i<N;++i)

    {

        if(p[i])

        {

            prime[ln++]=i;

            for(int j=i+i;j<N;j+=i)

            {

                p[j]=0;

            }

        }

    }

    for(int i=0;i<N;++i) dp[i]=-1.0;

    int T;

    scanf("%d",&T);

    for(int c=1;c<=T;++c)

    {

        int n;

        scanf("%d",&n);

        printf("Case %d: %.10lf\n",c,dfs(n));

    }

    return 0;

}