2010 Asia Regional Hangzhou Site —

2010 Asia Regional Hangzhou Site —— Online Contest

【题目链接】

HDU3641 Treasure Hunting

　　对ai进行质因子分解，然后在long long范围内二分找出题目所求最小x。

　　通过这道题学到了快速求阶乘包含某个因子的个数，下面是简要证明：

出处：http://www.cnblogs.com/cxiaojia/archive/2011/04/12/jiechengyinshifenjie.html

　　给定两个数m,n

　　求m!分解质因数后因子n的个数。

　　这道题涉及到了大数问题，如果相乘直接求的话会超出数据类型的范围。

　　下面给出一种效率比较高的算法，我们一步一步来。

　　m!=1*2*3*……*(m-2)*(m-1)*m

　　可以表示成所有和n倍数有关的乘积再乘以其他和n没有关系的

　　 =(n*2n*3n*......*kn)*other other是不含n因子的数的乘积因为 kn<=m 而k肯定是最大值所以k=m/n

　　 =n^k*(1*2*......*k)*other

　　=n^k*k!*other　　　　　

　　从这个表达式中可以提取出k个n，然后按照相同的方法循环下去可以求出k!中因子n的个数。

　　每次求出n的个数的和就是m!中因子n的总个数。

View Code

 1 #include <stdio.h>
 2 #include <string.h>
 3 #define N 105
 4 #define LL long long
 5 LL prime[N];
 6 
 7 void resolve(LL a, LL b)
 8 {
 9     LL i, j;
10     for(i = 2; i <= a; i ++)
11     {
12         if(!(a % i))
13         {
14             j = 0;
15             while(!(a % i))
16             {
17                 a /= i;
18                 j ++;
19             }
20             prime[i] += j * b;
21         }
22     }
23 }
24 
25 LL cal(LL p, LL v)
26 {
27     LL res = 0;  
28     while(v)
29     {
30         v /= p;
31         res += v;
32     }
33     return res;
34 }
35 
36 bool fit(LL v)
37 {
38     LL i;
39     for(i = 2; i < N; i ++)
40     {
41         if(prime[i] > 0)
42         {
43             LL tmp = cal(i, v);
44             if(tmp < prime[i])
45                 return false;
46         }
47     }
48     return true;
49 }
50 
51 int main()
52 {
53     LL t, a, b, n;
54     scanf("%I64d", &t);
55     while(t --)
56     {
57         scanf("%I64d", &n);
58         memset(prime, 0, sizeof prime);
59         while(n --)
60         {
61             scanf("%I64d%I64d", &a, &b);
62             resolve(a, b);
63         }
64         LL left = 0, right = (1ll << 62);
65         while(left <= right)
66         {
67             LL mid = (left + right) >> 1;
68             if(fit(mid))
69                 right = mid - 1;
70             else
71                 left = mid + 1;
72         }
73         printf("%I64d\n", right + 1);
74     }
75     return 0;
76 }

HDU3650 Hot Expo

贪心算法。首先根据起始时间对每个performance进行升序排序，每次选择可以在同一天内可以接着去看的且开始时间最早的performance。不断重复直到所有performance都看完，统计出所需天数即可。

View Code

 1  #include <stdio.h>
 2  #include <string.h>
 3  #include <algorithm>
 4  struct expo
 5  {
 6      int s, t;
 7  }e[101];
 8  
 9  bool flag[101];
10  int a;
11  
12  bool cmp(expo a, expo b)
13  {
14      return a.s == b.s ? (a.t < b.t ? 1 : 0): a.s < b.s ;
15  }
16      
17  
18  bool check(int n)
19  {
20      int i;
21      for(i = 0 ; i < n; i ++)
22          if(!flag[i])
23              break;
24      if(i == n)
25          return true;
26      a = e[i].t;
27      flag[i] = true;
28      return false;
29  }
30  
31  int main()
32  {
33      int n, i, cnt;
34      while(scanf("%d", &n), n)
35      {
36          memset(flag, false, sizeof(flag));
37          for(i = 0; i < n;i ++)
38              scanf("%d%d", &e[i].s, &e[i].t);
39          std::sort(e, e + n, cmp);
40          cnt = 0;
41          while(!check(n))
42          {
43              cnt ++;
44              for(i = 1; i < n; i ++)
45                  if(!flag[i] && e[i].s > a)
46                      flag[i] = true, a = e[i].t;
47          }
48          printf("%d\n", cnt);
49      }
50      return 0;
51  }