UVA11762 Race to 1

Race to 1

题目大意：给你一个正整数n，每次选不超过n的素数P，如果P | n,则n /= P。问把N变成1的期望操作次数

马尔科夫过程，即将状态转移看做一个FSM（有限状态机），每个状态用节点表示，转移用边表示，边权为转移概率

f[x]表示x变为1期望操作次数,p(x)表示小于等于x的素数个数，g[x]表示x中素因数个数

f[x] = 1 + f[x] * (1 - g[x]/p[x]) + Σ(y | x且y为素数)f[x/y] / p[x]

提出f[x]，有f[x] = (p[x] + Σ(y | x且y为素数)f[x/y])/g[x]

预处理p，√x求出g，记忆化搜索即可，总复杂度n√n + T

但f[x]中的x下降很快，真实计算量远远小于此

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <algorithm>
 6 #include <queue>
 7 #include <vector>
 8 #include <cmath> 
 9 #define min(a, b) ((a) < (b) ? (a) : (b))
10 #define max(a, b) ((a) > (b) ? (a) : (b))
11 #define abs(a) ((a) < 0 ? (-1 * (a)) : (a))
12 inline void swap(int &a, int &b)
13 {
14     long long tmp = a;a = b;b = tmp;
15 }
16 inline void read(int &x)
17 {
18     x = 0;char ch = getchar(), c = ch;
19     while(ch < '0' || ch > '9') c = ch, ch = getchar();
20     while(ch <= '9' && ch >= '0') x = x * 10 + ch - '0', ch = getchar();
21     if(c == '-') x = -x;
22 }
23 
24 const int INF = 0x3f3f3f3f;
25 const int MAXN = 1000000;
26 
27 int bp[MAXN + 10], prime[MAXN + 10], tot, p[MAXN + 10], b[MAXN + 10], t, ca, n;
28 double dp[MAXN + 10];
29 //p[x]表示不超过x的素数个数 g[x]表示x的因数个数
30 
31 void make_prime()
32 {
33     for(register int i = 2;i <= MAXN;++ i)
34     {
35         if(!bp[i]) prime[++tot] = i;
36         for(register int j = 1;j <= tot && i * prime[j] <= MAXN;++ j)
37         {
38             bp[i * prime[j]] = 1;
39             if(i % prime[j] == 0) break;
40         }
41     }
42 }
43 
44 double f(int x)
45 {
46     if(b[x]) return dp[x];
47     int tmp = sqrt(x), cnt = 0;
48     for(register int i = 1;i <= tmp;++ i)
49         if(x % i == 0)
50         {
51             if(!bp[x/i]) dp[x] += f(i), ++ cnt;
52             if(!bp[i] && i != x/i) dp[x] += f(x/i), ++ cnt;
53         }
54     dp[x] += (double)p[x];dp[x] /= (double)cnt;b[x] = 1;
55     return dp[x];
56 }
57 
58 int main()
59 {
60     read(t);
61     make_prime();
62     p[0] = p[1] = 0;
63     b[0] = b[1] = 1;
64     bp[1] = 1;
65     for(register int i = 2, now = 1;i <= MAXN;++ i)
66     {
67         p[i] = p[i - 1];
68         if(i == prime[now])++ now, ++ p[i];
69     }
70     for(ca = 1;t;-- t, ++ ca)
71     {
72         read(n);
73         printf("Case %d: %.10lf
", ca, f(n));
74     }
75     return 0;
76 }

UVA11762