Problem - 4430

　　題意是，給出蠟燭的數(shù)量，要求求出r和k，r是蠟燭的層數(shù)，k是每一層蠟燭數(shù)目的底數(shù)。

　　開始的時候，沒有看清題目，其實(shí)中間的那根蠟燭是可放可不放的。假設(shè)放置中間的那根蠟燭，就可以用等比數(shù)列求和公式S=(k^(r+1)-1)/(k-1)，因?yàn)檫@個公式，對于固定的r，S(k)是單調(diào)遞增的，然后可以發(fā)現(xiàn)，r的范圍是相當(dāng)?shù)男〉?#xff0c;最多不會大于40，然后就可以對于每一個r進(jìn)行一次二分查找，找到k。但是，對于r==1的時候，用這個公式的是會爆龍龍的，而r==1的時候又是直接可以計(jì)算出來的，所以留到之后再算。另外，求的是r*k最小的結(jié)果，其實(shí)很容易發(fā)現(xiàn)，r是越大越好的，所以就從大到小枚舉r進(jìn)行二分查找。如果都沒有找到可行解，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

?

　　看題真的要仔細(xì)，構(gòu)思以及敲這個代碼的時間是相當(dāng)少的，可是因?yàn)轭}意沒有看清，額外增加了十來分鐘的debug時間，感覺相當(dāng)不值啊！

?

——written by Lyon

?

轉(zhuǎn)載于:https://www.cnblogs.com/LyonLys/p/hdu_4430_Lyon.html

總結(jié)

以上是生活随笔為你收集整理的hdu 4430 Yukari's Birthday (简单数学 + 二分)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。