Uva_11762 Race to 1

题目链接

题意:

  给一个数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 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 浅入深出Vue:环境搭建

    这里同样的,有固态硬盘的童鞋可以安装到固态硬盘,不过这里有个小问题就是 在选择目录的时候会卡死一小会儿。可能是若羽的机器性能不太好。

    若羽
  • Uva_11462 GCD - Extreme (II)

      给定一个n, 求:GCD(1, 2) + GCD(1, 3) + GCD(2, 3) + …… + GCD(1, n) + GCD(2, n) + …… +...

    若羽
  • LightOJ_1038 Race to 1 Again

      给一个数n, 每次操作是随机的选择一个[1,N]区间内能够被n整除的数进行除法, 然后得到一个新的n。

    若羽
  • PE刷题记

    开始以为有单调性,也就是如果长度为$x$的能构成素数,那$x - 1$一定能构成素数

    attack
  • count_if函数的用法

    用户7727433
  • 【LightOJ 1136】Division by 3(简单数学)

    1, 12, 123, 1234, ..., 12345678910, ... 问第a到第b个数(inclusive)里有几个可以被3整除。

    饶文津
  • hihoCoder 1700 相似颜色

            题目链接: http://hihocoder.com/problemset/problem/1700

    Ch_Zaqdt
  • 暑假(补)-1

    GCD是求最大公约数,有两种方法:1.自己构建函数。2.头文件中的__gcd()函数.

    AngelNH
  • 策略模式(Strategy)

    - 1.Strategy:策略接口,用来约束一系列具体的策略算法。Context使用这个接口来调用具体的策略,实现定义的策略。

    qubianzhong
  • HDU 6370 Werewolf(并查集+dfs) 18年暑假多校赛第六场

    讲解博客:http://www.cnblogs.com/curieorz/p/9447454.html

    用户2965768

扫码关注云+社区

领取腾讯云代金券