首页 > 代码库 > hdu 4430 Yukari's Birthday（二分）

hdu 4430 Yukari's Birthday（二分）

2024-07-14 14:51:07   225人阅读

Yukari‘s Birthday

Time Limit: 12000/6000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2703    Accepted Submission(s): 556


Problem Description
Today is Yukari‘s n-th birthday. Ran and Chen hold a celebration party for her. Now comes the most important part, birthday cake! But it‘s a big challenge for them to place n candles on the top of the cake. As Yukari has lived for such a long long time, though she herself insists that she is a 17-year-old girl.
To make the birthday cake look more beautiful, Ran and Chen decide to place them like r ≥ 1 concentric circles. They place ki candles equidistantly on the i-th circle, where k ≥ 2, 1 ≤ i ≤ r. And it‘s optional to place at most one candle at the center of the cake. In case that there are a lot of different pairs of r and k satisfying these restrictions, they want to minimize r × k. If there is still a tie, minimize r.
 

Input
There are about 10,000 test cases. Process to the end of file.
Each test consists of only an integer 18 ≤ n ≤ 1012.
 

Output
For each test case, output r and k.
 

Sample Input
18
111
1111
 

Sample Output
1 17
2 10
3 10
 

Source
2012 Asia ChangChun Regional Contest
 

题解及代码：

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
typedef __int64 LL;

LL sum(LL k,LL r,LL n)        //求∑k^i
{
    LL ans=0,t=k;
    for(int i=0;i<r;i++)
    {
        ans+=t;
        t*=k;
        if(ans>n) return n+1;    //∑k^i的一部分值已超出n
                                 //就不用再计算，返回n+1即可
    }
    return ans;
}

bool judge(LL r,LL _l,LL _r,LL &k,LL n) //使用二分求出当前r对应的k值
{
    LL t;
    while(_l<=_r)
    {
        k=(_l+_r)/2;
        t=sum(k,r,n);
        if(t==n)
        {
            return true;
        }
        else if(t<n) _l=k+1;
        else if(t>n) _r=k-1;
    }
    return false;
}
int main()
{
    LL n;

    while(scanf("%I64d",&n)!=EOF)
    {
        LL R=1,K=2;
        for(;K<(n+2)/2;K<<=1)      //求出最大的圈数，即每圈放两个蜡烛
        {
            R++;
        }
        LL r,k;
        LL rr=1e7,kk=1e7,_l=2,_r=n,t;
        for(r=1;r<=R;r++)
        {
             _l=2,_r=(LL)pow(double(n+1),1.0/(double)r); //给出左右边界
             if(judge(r,_l,_r,k,n))     //求出当前r下，最中心不放蜡烛的k
             {
                 if(r*k<rr*kk||(r*k==rr*kk&&r<rr))
                    rr=r,kk=k;
             }
             if(judge(r,_l,_r,k,n-1))   //求出当前r下，最中心不放蜡烛的k
             {
                 if(r*k<rr*kk||(r*k==rr*kk&&r<rr))
                    rr=r,kk=k;
             }
        }
        printf("%I64d %I64d\n",rr,kk);
    }
    return 0;
}
/*
题目的意思是，一个蛋糕上放n跟蜡烛，第一圈假设放k个，那么第二圈最多放k*K个……
直到所有的蜡烛都放完，每圈最少放2根，最中间可以放一根也可以不放，求圈数r和k，
如果有多种情况，那么保证r*k最小，如果还有多种情况，保证r最小。

由于每圈最少放两根，为了保证r*k最小，那么我们保证除了最后一圈，其他都放满，这样
我们就能求出最大的圈数R，那么我们就可以枚举圈数r来计算慢去情况的k

这里我们需要用二分来查找最小的k，k的最小值为2，那么左边界为2，接下来我们求右边界，
利用等比数列的求和公式sum=a1*(k^r-1)/k-1=k*(k^r-1)/k-1;这里sum=n和r均是已知值，来求k是可以做到的
但是求解起来比较困难，所以我们要使用放缩的方法，这里sum'=k^r-1,可以看到sum'<sum=n
那么我们用n来代替sum'，之后得到的k'是大于k的，扩大了寻找范围，但是不会漏掉情况
那么右边界的求法就是r=(LL)pow(double(n+1),1.0/(double)r); 

由于中间可以放也可以不放，那么我们就分开来求k就可以了，然后再比较得出最优情况。

*转载请注明出处，谢谢。
*/


联系
我们