题意:
给一个数n, 每次从小于等于n的素数里选一个P, 如果能被n整除, 那么就n就变成n / P。
问: n 变成1的期望。
思路:
设小于等于n的素数有p 个, 其中是n的约数的有g个。
则E[x] = 1 + 1/p * (1 - g/p) + sigma(i = 0, 1, 2, g)num[i] * 1/p。
化简得:
E[x] = (p + sigma(i = 0, 1, 2, g)num[i]) / g。
代码如下:
1 #include <cmath>
2 #include <cstdio>
3 #include <cstring>
4 #include <cstdlib>
5 #include <ctime>
6 #include <set>
7 #include <map>
8 #include <list>
9 #include <queue>
10 #include <string>
11 #include <vector>
12 #include <fstream>
13 #include <iterator>
14 #include <iostream>
15 #include <algorithm>
16 using namespace std;
17 #define LL long long
18 #define MAXN 1000010
19 #define MOD 1000000007
20 #define eps 1e-6
21 int prime_size;
22 int prime_[MAXN];
23 double f[MAXN];
24 bool prime[MAXN], vis[MAXN];
25 int n;
26 bool is_prime(int x)
27 {
28 if(x <= 1) return false;
29 for(int i = 2; i * i <= x; i ++)
30 if(x % i == 0) return false;
31 return true;
32 }
33 void p_init()
34 {
35 memset(vis, false, sizeof(vis));
36 prime_size = 0;
37 for(int i = 2; i < MAXN; i ++)
38 if(is_prime(i))
39 {
40 prime_[prime_size ++] = i;
41 for(int j = 1; j * i < MAXN; j ++)
42 prime[j * i] = true;
43 }
44 f[0] = f[1] = 0;
45 }
46 double dp(int x)
47 {
48 if(x == 1) return 0.0;
49 if(vis[x]) return f[x];
50 vis[x] = true;
51 int g = 0;
52 int p = 0;
53 double& ans = f[x];
54 ans = 0;
55 for(int i = 0; i < prime_size && prime_[i] <= x; i ++)
56 {
57 p ++;
58 if(x % prime_[i] == 0)
59 {
60 g ++;
61 ans += dp(x / prime_[i]);
62 }
63 }
64 ans = (ans + p) / g;
65 return ans;
66 }
67
68 int main()
69 {
70 int T;
71 int kcase = 0;
72 p_init();
73 scanf("%d", &T);
74 while(T --)
75 {
76 scanf("%d", &n);
77 printf("Case %d: %.7lf\n", ++ kcase, dp(n));
78 }
79 return 0;
80 }