hdu_4430，二分

注意处理溢出
#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

long long n;

long long a[60][2];

int k;

int fun(long long y,int x)

{

    long long cnt=0,cur=1;

    for(int i=1; i<=x; i++)

    {

        if(n/cur<y) return 1;

        cur*=y;

        cnt+=cur;

        if(cnt>n)

        {

            return 1;

        }

    }

    if(cnt==n-1||cnt==n)

    {

        a[k][0]=y;

        a[k][1]=x;

        k++;

        return 0;

    }

    if(cnt<n)

    {

        return 2;

    }

}

void solve(int x)

{

    long long lb=1,ub=n;

    while(ub-lb>1)

    {

        long long mid=(ub+lb)/2;

        if(fun(mid,x)==0) break;

        else if(fun(mid,x)==1)

        {

            ub=mid;

        }

        else lb=mid;

    }

}

int main()

{

    while(cin>>n)

    {

        memset(a,0,sizeof(a));

        k=0;

        for(int i=0; i<60; i++)

        {

            solve(i);

        }

        long long ans=a[0][0]*a[0][1];

        long long x=a[0][0],y=a[0][1];

        for(int i=0; a[i][0]!=0; i++)

            if(a[i][0]*a[i][i]<ans)

            {

                ans=a[i][0]*a[i][1];

                x=a[i][0];

                y=a[i][1];

            }

        printf("%I64d %I64d\n",y,x);

    }

    return 0;

}
巴特西

hdu_4430，二分

最新文章

热门文章
