這是一個(gè)很神的數(shù)學(xué)題吧。基本上過這個(gè)題的很多都會(huì)wa10多次，而且這個(gè)題好像簡(jiǎn)單的枚舉其中的一個(gè)指數(shù)值都能過，可能是
數(shù)據(jù)量比較小。
但是，這個(gè)題還是有數(shù)學(xué)的解法的。但是，即使找到了這個(gè)正確的解法，過題的話，也是一件很困難的事情。題意大致如下：一只貓，
高度為H，戴了一個(gè)帽子，帽子里面有N只貓（N是常數(shù)，且未知），同樣帽子里面的貓也戴了帽子，但是這些貓的高度變成了H / (N + 1)，
會(huì)向下取整。以此遞歸下去，直到最后的貓的高度都為1為止。現(xiàn)在，給出H和高度為1的貓的數(shù)量。要求的是高度大于1的貓的數(shù)量，
以及所有貓的高度之和。
很別扭吧。通過上面的信息，得出2個(gè)式子。假設(shè)one代表為高度為1的貓的數(shù)量。one = N的n次。H >= (N + 1)的n次。注意第
二個(gè)式子不一定取等號(hào)，因?yàn)楹芏鄷r(shí)候都是不能整除的。現(xiàn)在要求N和n。2個(gè)方程解2個(gè)未知數(shù)，應(yīng)該能解出來。但是，注意的是其中
一個(gè)還是不等式。。。
指數(shù)關(guān)系很多時(shí)候會(huì)轉(zhuǎn)換為對(duì)數(shù)的關(guān)系。所以，繼續(xù)求對(duì)數(shù)，有l(wèi)gH >= n * lg(N + 1)。其中，由第一個(gè)式子可以得到n = lg(one)
/ lg(N)。那么最終轉(zhuǎn)換為：lgH >= (lg(one) / lgN) * lg(N + 1)。換個(gè)形式就是lgH / lg(One) >= lg(N + 1) / lgN。現(xiàn)在，已經(jīng)很
清晰了。因?yàn)椋瘮?shù)lg(N + 1) / lg(N) 是
單調(diào)遞減的。看到單調(diào)的函數(shù)，馬上就會(huì)知道可以二分了。意思是，我們可以二分出一個(gè)N讓
lg(N + 1) / lgN 最接近lgH / lg(One)，而且是小于lgH / lg(One)的。剩下的工作就只是求和而已了。
寫二分的時(shí)候，有一個(gè)地方可以注意一下。因?yàn)?nbsp;lg(N + 1) / lgN 可能會(huì)出現(xiàn)除數(shù)為0的情況，所以可以進(jìn)一步轉(zhuǎn)換為
lgH * lgN >=
lg(N + 1) * lg(one)。 也是求一個(gè)N讓上面那個(gè)不等式2邊的值最接近，而且右邊小于左邊。
能很快寫對(duì)這個(gè)題真不是件容易的事情。。。
代碼如下：
#include <stdio.h>
#include <math.h>
int main()
{
int nInitH, nOnes;
int nN, n;
while (scanf("%d%d", &nInitH, &nOnes), nInitH + nOnes)
{
int nBeg = 1;
int nEnd = nOnes;
int nMid;
while (nBeg <= nEnd)
{
nMid = (nBeg + nEnd) / 2;
double fRes = log10(nInitH) * log10(nMid);
double fTemp = log10(nMid + 1) * log10(nOnes);
if (fabs(fRes - fTemp) < 1e-10)
{
//printf("Find nN:%d\n", nMid);
nN = nMid;
break;
}
else if (fTemp > fRes)
{
nBeg = nMid + 1;
}
else
{
nEnd = nMid - 1;
}
}
n = floor(log10(nInitH) / log10(nN + 1) + 1e-9);
//printf("nN:%d, n:%d\n", nN, n);
int nSum = 0;
int nLazy = 0;
int nNum = 1;
for (int i = 0; i <= n; ++i)
{
nSum += nNum * nInitH;
nLazy += nNum;
nNum *= nN;
nInitH /= (nN + 1);
}
printf("%d %d\n", nLazy - nOnes, nSum);
}
return 0;
}