UVA11762 Race to 1

题意：给定一个数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; } ```