UVA11762 Race to 1
给定一个数n,每次可以将它除以一个小于它的质数,也可以不动,问变成1的期望步数
エロ発生:打素数表打小了1
Solution
一眼看记忆化搜索实现期望转移
设到 \(i\) 的期望步数为 \(dp[i]\) ,则他的转移有两种情况嘛:
第一种是没摇到质因子, 转了回来 也就是 \(dp[i]\) 乘上转回来的概率
第二种情况随到了质因子, nice, 转移就是 \(dp[i] += dp[i / p]\) 乘转到他的概率
所以化简一下拿记忆化搜出来就行
Code
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#include<climits>
#define LL long long
#define REP(i, x, y) for(int i = (x);i <= (y);i++)
using namespace std;
int RD(){
int out = 0,flag = 1;char c = getchar();
while(c < '0' || c >'9'){if(c == '-')flag = -1;c = getchar();}
while(c >= '0' && c <= '9'){out = out * 10 + c - '0';c = getchar();}
return flag * out;
}
const int maxn = 1e6 + 10;
int T, n, Tony;
double dp[maxn];
int prime[maxn], nump;
bool vis[maxn];
void get_prime(){
memset(vis,0,sizeof(vis));
for(int i = 2;i <= maxn - 5;i++){
if(!vis[i])
prime[++nump]=i;
for(int j = 1;(j <= nump)&&(i * prime[j] < maxn - 5);j++){
vis[i * prime[j]] = 1;
if(i % prime[j] == 0)
break;
}
}
}
double DP(int x){
if(x == 1)return 0;
if(dp[x] != 0)return dp[x];
int cnt = 0, cnt_p = 0;
for(int i = 1;i <= nump && prime[i] <= x;i++){
cnt++;
if(x % prime[i] == 0){
cnt_p++;
dp[x] += DP(x / prime[i]);
}
}
dp[x] = (dp[x] + cnt) / cnt_p;
return dp[x];
}
void init(){
n = RD();
}
void work(){
printf("Case %d: %.10lf\n", ++Tony, DP(n));
}
int main(){
get_prime();
T = RD();
while(T--){
init();
work();
}
return 0;
}