枚举r,然后用二分来求对应的k.
因为题目上k>=2,所以r肯定不会很大,二分就可以了.
需要注意的是二分时初始右边界不能太大,不然会导致计算过程超出long long
还有就是提交时输入输出在zoj上要要用%lld,而hdu要用%I64d,不然会Wrong Answer
代码:
[cpp]
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
long long powLL(long long a,int b){
long long res=1;
for(int i=0;i<b;i++)
res*=a;
return res;
}
int main(void){
long long n,r,k;
while(scanf(“%lld”,&n)!=EOF){
r=1;
k=n-1;
for(int i=2;i<=45;i++){
long long ll,rr,mm;
ll=2;
rr=(long long)pow(n,1.0/i);
while(ll<=rr){
mm=(long long)(ll+rr)/2;
long long ans=(mm-powLL(mm,i+1))/(1-mm);
if(ans==n||ans==n-1){
if(i*mm<r*k){
r=i;
k=mm;
}
break;
}
else if(ans>n){
rr=mm-1;
}
else {
ll=mm+1;
}
}
}
printf(“%lld %lld\n”,r,k);
}
return 0;
}