hdu4430:http://acm.hdu.edu.cn/showproblem.php?pid=4430
题意：题目的意思就是给你一个s，让你求k,r，其中k,r,满足：k^1+k^2+.....+k^r==s||s-1,并且k*r是最小的，如果有多种情况,r是最小的。
题解：一开始不知道怎么做，听别人说是二分。然后开始往二分上想。
思维过程：一开始就想着怎么二分，首先二分必须找到一个线性关系，找了半天也没有找到什么线性关系，所以不知道怎么二分，也不知道二分什么变量。想了很久，最后看到k*r最小，k是底数，r是指数，所以当r最大时候，k是最小的，同时k*r是最小的，因为k是指数增长的，，当r很大，k只要很小就可以达到s.当k==2的时候，r最多只要40就可以达到s。所以可以枚举r了，然后来找k。这样就慢慢想到，对于固定r，k越大，它的次方和也是随着增大的，所以线性关系出来了，可以二分k，k初始值是s||s-1,所以分两种情况来做，就可以了。不过，这里还要处理一些益处问题，在计算次方和的时候，如果底数大于1e7,其他的值也行，只要不小于1e6就直接跳出，不用计算。具体的，代码中有注释。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
long long n;
long long k,ans1,lastr,lastk,l,mid,r;
bool judge(long long s,int num,long long flag){
long long ans=,temp=s;
if(s>)return true;//这里是特判，方式爆出long long 因为如果这个数>1e7的话，她的平方必然大于n(考虑n范围)
for(int i=;i<=num;i++){
ans+=temp;
temp*=s;
if(ans>=flag)return true;//这里也是防止溢出
}
return false;
}
bool judge2(long long s,int num){//判断这个数是不是要找的数
long long ans=,temp=s;
if(s>)return false;
for(int i=;i<=num;i++){
ans+=temp;
temp*=s;
if(ans>n)return false;
}
if(ans==n||ans==n-)return true;
return false;
}
int main(){ while(~scanf("%I64d",&n)){
ans1=n-;lastr=;lastk=n-;
for(int i=;i<=;i++){
l=,r=n;
while(l<r){//二分的结果是要么找到了==n的数，要么循环退出
mid=(l+r)/;
if(judge(mid,i,n))
r=mid;
else
l=mid+;
}
if(judge2(l,i)&&ans1>i*l){//检查是否是找到==n的那个数
ans1=i*l;
lastr=i;
lastk=l;
}
l=,r=n-;
while(l<r){//要么找到==n-1的数，要么退出循环
mid=(l+r)/;
if(judge(mid,i,n-))
r=mid;
else
l=mid+;
}
if(judge2(l,i)&&ans1>i*l){//同上
ans1=i*l;
lastr=i;
lastk=l;
}
}
printf("%I64d %I64d\n",lastr,lastk);
}
}