HDU 4430 - Yukari's Birthday (二分 + 思维)

题意

给出N个蜡烛,问可以摆成多少个同心圆,每个同心圆的基准数是k。条件为r*k尽量小。

思路

分析得r最多为40。

又因为k有单调性,所以就二分了。

代码

LL Solve(int level, LL n)
{
    LL l = 2, r = (LL)pow(n, 1.0/level);
    while (l <= r)
    {
        LL mid = MID(l, r);
        LL cur = 1, sum = 0;
        for (int i = 1; i <= level; i++)
        {
            cur *= mid;
            sum += cur;
            if (sum > n) break;
        }
        if (sum == n) return mid;
        else if (sum > n) r = mid-1;
        else l = mid+1;
    }
    return 0;
}
 
int main()
{
    //ROP;
    LL n;
    while (~scanf("%lld", &n))
    {
        LL ansr, ansk, ans = (1ll<<62);
        for (int r = 1; r <= 40; r++)
        {
            LL tmp = Solve(r, n);
            if (tmp && ans > tmp*r)
            {
                ans = tmp*r;
                ansr = r, ansk = tmp;
            }
            tmp = Solve(r, n-1);
            if (tmp && ans > tmp*r)
            {
                ans = tmp*r;
                ansr = r, ansk = tmp;
            }
        }
        printf("%lld %lld\n", ansr, ansk);
    }
    return 0;
}

Powered by Jekyll and Theme by solid