题意:
给一个数n, 每次操作是随机的选择一个[1,N]区间内能够被n整除的数进行除法, 然后得到一个新的n。
问n变成1时的期望操作次数。
思路:
设E[n] 为 当数为x时, 变成 1 期望的次数, 则有转移方程。
E[n] = sigma E[n / x[i]] / k + 1(x[i] 为能被n被整除的数), k为n在区间[1,n]能被n整除的个数。
化简:E[n] = E[n] / k + sigma E[n / x[i]] / k + 1
= k * (sigmaE[n / x[i]] / k + 1) / (k - 1)
= (sigmaE[n / x[i]] + k) / (k - 1)。
代码:
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 100010
19 #define MOD 1000000007
20 #define eps 1e-6
21 int n;
22 double f[MAXN];
23 bool vis[MAXN];
24 vector <int> g[MAXN];
25 void init()
26 {
27 for(int i = 2; i < MAXN; i ++)
28 for(int j = 1; j * i < MAXN; j ++)
29 g[j * i].push_back(i);
30
31 f[1] = 0;
32 memset(vis, false, sizeof(vis));
33 }
34 double dp(int x)
35 {
36 if(x == 1) return 0.0;
37 if(vis[x]) return f[x];
38 vis[x] = true;
39 double& ans = f[x];
40 ans = 0.0;
41 for(int i = 0; i < g[x].size(); i ++)
42 ans += dp(x/g[x][i]);
43 ans += (g[x].size() + 1.0);
44 ans /= g[x].size();
45 return ans;
46 }
47
48 int main()
49 {
50 int T;
51 int kcase = 0;
52 init();
53 scanf("%d", &T);
54 while(T --)
55 {
56 scanf("%d", &n);
57 printf("Case %d: %.7lf\n", ++ kcase, dp(n));
58 }
59 return 0;
60 }