HDU-4430-Yukari's Birthday-暴力+二分

アドレス:http://acm.hdu.edu.cn/showproblem.php?pid=4430
タイトル:
君に一つあげる 18 ≤ n ≤ 10 12. 
あなたはr,kを出力して、まず1+k^1+k^2+...+k^r=nあるいはn+1を満たして、そしてkの範囲はk>=2です;//複数がr*kの最小を満たす場合、複数がある場合はrの最小をとる
 k最小が2であることから,r最大は40を超えないことが分かった.1+2^40は10^12に近いからである.
そして明らかに式の左側は等比数列であり,簡略化され,(k^r−1)/(k−1)=n
明らかに,k>1が左側に対して単調に増加する関数である場合,r,nが決定すると,我々は2分kだけでよい.
kの範囲は【2,10^12】
一つは、関数を書くべきだと判断することです.  if ((pow(k,r+1)-1)/(k-1)-n >eps   )
しかしその时、脳が不自由になって何を考えているのか分からないが、k-1を右に移してpow(k,r+1)-1)-(k-1)*nになった. //k=n=10^12の時、爆発します!
主に注意powここで判断が等しいか大きいかはepsで...そしてk-1を右に置かないように注意すればいい!

#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <cfloat> 
#include <algorithm>
#include <iostream>
#include <queue>
#include <map>
#include <set>
#include <vector>
using namespace std;
__int64 maxx= 9223372036854775807;
#define eps 0.01

__int64 ans_r;
__int64 ans_k; 
int main()
{   
	 __int64 n; 	
	
	__int64 slove1 (__int64 n);  //n+1
	while(	scanf("%I64d",&n)!=EOF)
	{

		//	maxx=n-1;
		maxx= 9223372036854775807;
	ans_r=1;
	ans_k=n-1;
	slove1(n);
	slove1(n+1);

	printf("%I64d %I64d
",ans_r,ans_k);
	
	}
	return 0;
	
}

__int64 ok(__int64 k,__int64 r,__int64 n)
{ 
	if ((pow(k,r+1)-1)/(k-1)-n >eps   )
		return 1;
	else
		return 0;
}

__int64 slove1(__int64 n)
{
	int i;
	for (i=1;i<=40;i++)
	{
		__int64 l=2;
		__int64 r=pow(10.0,12);
		while(l<r)  
        {  
            __int64 mid=(l+r)/2;  
            if (r-l==1)  
            {  
                if ((!  (fabs((pow(r,i+1)-1)/(r-1)-n)<eps)  ) )     
					r=l;  
                break;   
            }  
            if (ok(mid,i,n))
				r=mid-1;        
            else  
                l=mid;      
			
        }  
		if (  fabs((pow(r,i+1)-1)/(r-1)-n)<eps   )     
		{
			__int64 tmp=i*r;
			if (tmp<maxx)
			{
				maxx=tmp;
				ans_r=i;
				ans_k=r;
			}
			else
				if(tmp==maxx)
				{
					if (i<ans_r)
					{
						ans_r=i;
						ans_k=r;
					}
				} 
		}
		
	} 
	return 0;
}

.