UVA11762 Race to 1

2018-09-04 11:05:43


题意:给定一个数n,每次可以将它除以一个小于它的质数,也可以不动,问变成1的期望步数

期望dp,可以用记忆化搜索实现

和一般的期望题目类似,定义 $f[i]$ 表示从 $i$ 到 $1$ 的期望步数

用 $num$ 表示小于 $i$ 的质数的个数, $tot$ 表示小于 $i$ 且能整除 $i$ 的质数的个数

转移方程可表示为: $f[i]=f[i]*(num-tot)/num+f[i/j]/num+1$

其中 $j$ 是枚举出的小于 $i$ 且能整除 $i$ 的质数

化简后记忆化搜索即可

注意多组询问不需要清空数组,因为每一个数的答案是固定的

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e6+5;
int prime[N/10],cnt;
double f[N];
bool prim[N];
inline void Get_Prime()
{
    for (int i=2;i<=N-5;i++)
    {
        if (!prim[i]) prime[++cnt]=i;
        for (int j=1;j<=cnt&&i*prime[j]<=N-5;j++)
        {
            prim[i*prime[j]]=1;
            if (i%prime[j]==0) break;
        }
    }
}
double dfs(int x)
{
    if (x==1) return 0;
    if (f[x]) return f[x];
    int num=0,tot=0;
    for (int i=1;i<=cnt&&prime[i]<=x;i++)
    {
        ++num;
        if (x%prime[i]==0) ++tot,f[x]+=dfs(x/prime[i]);
    }
    return f[x]=(f[x]+num)/tot;
}
int main()
{
    int T; scanf("%d",&T); Get_Prime();
    for (int t=1;t<=T;t++)
    {
        int x; scanf("%d",&x);
        printf("Case %d: %.10lf\n",t,dfs(x));
    }
    return 0;
}