hdu 4430 Yukari's Birthday (简单数学 + 二分)

　　题意是，给出蜡烛的数量，要求求出r和k，r是蜡烛的层数，k是每一层蜡烛数目的底数。

　　开始的时候，没有看清题目，其实中间的那根蜡烛是可放可不放的。假设放置中间的那根蜡烛，就可以用等比数列求和公式S=(k^(r+1)-1)/(k-1)，因为这个公式，对于固定的r，S(k)是单调递增的，然后可以发现，r的范围是相当的小的，最多不会大于40，然后就可以对于每一个r进行一次二分查找，找到k。但是，对于r==1的时候，用这个公式的是会爆龙龙的，而r==1的时候又是直接可以计算出来的，所以留到之后再算。另外，求的是r*k最小的结果，其实很容易发现，r是越大越好的，所以就从大到小枚举r进行二分查找。如果都没有找到可行解，r==1的时候就唯一解了，所以之前是不用搜索r==1的情况的。

代码如下：

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <algorithm>
 4 #include <cmath>
 5 
 6 using namespace std;
 7 typedef long long LL;
 8 
 9 const LL INF = 9000000000000000000ll;
10 
11 LL cal(LL k, int r) {
12     LL ret = 1ll;
13     while (r > 0) {
14         if (r & 1) ret *= k;
15         k *= k;
16         r >>= 1;
17     }
18     return ret;
19 }
20 
21 LL find(LL x, int ep) {
22     LL h = 2ll, t = (LL) pow((double) INF, 1.0 / ep), mk = -1ll;
23     while (h <= t) {
24         LL m = h + t >> 1, tmp = cal(m, ep) - 1;
25         if (tmp / (m - 1) < x) h = m + 1;
26         else {
27             t = m - 1;
28             if (tmp % (m - 1)) continue;
29             if (tmp / (m - 1) == x || tmp / (m - 1) == x + 1) mk = m;
30         }
31     }
32     return mk;
33 }
34 
35 int main() {
36     LL x;
37     while (cin >> x) {
38         LL a = -1ll, b;
39         for (int i = 50; i > 1; i--) {
40             b = find(x, i + 1);
41             if (b > 0) {
42                 a = i;
43                 break;
44             }
45         }
46         if (~a) cout << a << ' ' << b << endl;
47         else cout << 1 << ' ' << x - 1 << endl;
48     }
49     return 0;
50 }

View Code

　　看题真的要仔细，构思以及敲这个代码的时间是相当少的，可是因为题意没有看清，额外增加了十来分钟的debug时间，感觉相当不值啊！

——written by Lyon