HDU 4430 Yukari's Birthday 二分，hduyukari

HDU 4430 Yukari's Birthday 二分，hduyukari

給出n，讓n滿足下列表達式：k^1+k^2+...+k^r=n. 且r*k要最小。(ps: And it's optional to place at most one candle at the center of the cake. 所以k^0，即1可有可無。但是這並不算一個圓，所以當n=30和n=31時，它們的r相等)  例如：2^1+2^2+2^3+2^4=30. n=30,r=4,k=2. (n=31時，r也為4，k也為2)  所以就有通解r=1,k=n-1. 這對於每個n都成立。不過我們得讓r*k最小，就得都遍歷一遍了。

因為2^0+2^1+2^2+...+2^40=2^41-1>10^12. 所以1<=r<=40. r不是很大，直接暴力。k通過二分來找。

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;

const long long inf=1000000000001;
int main()
{
    //freopen("in.txt","r",stdin);
    long long n;
    while(scanf("%I64d",&n)!=EOF)
    {
        int min_r;
        long long min_k,min_v=inf;
        for(int r=1; r<=40; r++)
        {
            long long low=1,high=n,k;
            while(1)
            {
                k=(low+high)/2;
                long long sum=0;
                bool flag=true;
                for(int i=1; i<=r; i++)
                    if(pow(k*1.0,i)>n) //此處是判讀那看k^i是否大於n，如果大於，就不用再求和了
                    {
                        sum=n+1;
                        flag=false;
                        break;
                    }
                if(flag)
                    for(int i=1; i<=r && sum<=n; i++)
                        sum+=(long long)pow(k*1.0,i);
                if(sum==n || sum==n-1) //因為1可有可無，所以滿足其中一個條件即可
                    if(r*k<min_v)
                    {
                        min_r=r;
                        min_k=k;
                        min_v=r*k; //保存最小乘積
                    }
                if(sum>n)
                    high=k;
                else
                    low=k;
                if(high-low==1)
                    break;
            }
        }
        printf("%d %I64d\n",min_r,min_k);
    }
    return 0;
}