zoj3665长春K

gistfile1.cpp

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;
typedef long long LL;

LL n,r,k;
LL ansk,ansr,Max;

LL bsch1(LL r,LL n){
    LL ll,rr,mid;
    ll=2;rr=n-1;
    LL i;
    LL flag=0;
    while(ll<=rr){
        mid=(ll+rr)/2;
        LL tmp=mid;
        flag=1;
        for(i=1;i<r;i++){
            if (tmp>n/mid)  {flag=0;break;}
            tmp=(tmp+1)*mid;
        }
        
        if (flag==0) {rr=mid-1;continue;}
            
        if(tmp<n){ll=mid+1;}
        else if(tmp>n) rr=mid-1;
        else return mid;
    }
    return -1;
}


int main()
{
    while(~scanf("%lld",&n)){
        ansk=n-1;ansr=1;Max=ansk*ansr;
        for(r=2;r<=42;r++){
            k=bsch1(r,n);
            if(k!=-1) {
                if((k*r<Max)||(Max==k*r&&ansr>r)){
                    ansk=k,ansr=r,Max=k*r;
                }
            }
            k=bsch1(r,n-1);
            if (k!=-1){
                if((k*r<Max)||(Max==k*r&&ansr>r)){
                    ansk=k,ansr=r,Max=k*r;
                }
            }
            
        }
        printf("%lld %lld\n",ansr,ansk);
    }
    return 0;
}