首页 > 代码库 > HDU 4430 Yukari's Birthday(枚举+二分)

HDU 4430 Yukari's Birthday(枚举+二分)

2024-08-04 14:07:02   220人阅读

题目大意：给你你个n， 圆心放一个蜡烛，之后每一圈放k^i个，i = 1，2，3，4，5…….。求出来圈数r，第一圈的k的乘积最小，如果相同的时候求r最小。

10000组数据暴力果断TLE，后来发现r很小，可以暴力枚举r然后二分k。

Yukari‘s Birthday

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


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 <algorithm>
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <iomanip>
#include <stdio.h>
#include <string>
#include <queue>
#include <cmath>
#include <time.h>
#include <stack>
#include <map>
#include <set>
#define eps 1e-8
#define M 1000100
///#define LL long long
#define LL __int64
#define INF 0x3f3f3f
#define PI 3.1415926535898
#define mod 1000000007


using namespace std;

const int maxn = 1010;

LL Get(int x, LL n, LL ns)
{
    LL s = 1LL;
    for(int i = 1; i <= x; i++)
    {
        s *= n;
        if(n*(1LL-s)/(1LL-n) > ns) return -1;
    }
    return n*(1LL-s)/(1LL-n);
}


LL Find(int x, LL n)
{
    LL l = 2LL;
    LL r = (LL)pow(n, 1.0/x);
    while(l <= r)
    {
        LL mid = (l+r)>>1;
        LL x1 = Get(x, mid, n);
        if(x1 == -1LL)
        {
            r = mid-1LL;
            continue;
        }
        if(x1 == n || x1 == n-1) return mid;
        else if(x1 > n-1LL) r = mid-1LL;
        else if(x1 < n-1LL) l = mid+1LL;
    }
    return -1;
}

int main()
{
    LL n;
    while(~scanf("%I64d",&n))
    {
        LL Min = n-1;
        LL xi = 1LL;
        LL yi = n-1LL;
        LL ans = 0LL;
        while((1LL<<(ans)) < n) ans++;
        for(LL i = 1LL; i <= ans; i++)
        {
            LL x = Find(i, n);
            if(x == -1) continue;
            if(Min > x*i)
            {
                Min = x*i;
                xi = i;
                yi = x;
            }
            else if(Min == x*i)
            {
                if(xi > i)
                {
                    xi = i;
                    yi = x;
                }
            }
        }
        cout<<xi<<" "<<yi<<endl;
    }
    return 0;
}


HDU 4430 Yukari's Birthday(枚举+二分)


联系
我们