首页 > > 程序设计 > C/C++ >

HDU 4430 Yukari's Birthday 二分

2018-06-17 23:54:23来源：未知阅读 ()

给出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;
}

还没完，我后来又优化了下。(*^__^*) 嘻嘻……

#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=1;
        long long min_k=n-1,min_v=n-1;
        for(int r=2; r<=40; r++)
        {
            long long low=1,high=pow(n,1.0/r),k;
            while(low<=high)
            {
                k=(low+high)/2;
                long long sum=0;
                long long temp=1;
                for(int i=1; i<=r; i++)
                {
                    temp=temp*k;
                    sum+=temp;
                }
                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-1;
                else
                    low=k+1;
            }
        }
        printf("%d %I64d\n",min_r,min_k);
    }
    return 0;
}