HDU 4430 Yukari's Birthday 二分

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

新老客户大回馈,云服务器低至5折

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

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:Token的设计(2)

下一篇:实现一门新的语言--背景(1)