HDU 4430：Yukari's Birthday——二分確定同心圓蠟燭分布

問題

在蛋糕上放 n 支蠟燭，形成 r≥1 個同心圓，第 i 圓放 k^i 支（k≥2），圓心可選放 0 或 1 支。最小化 r*k，次優先最小化 r。18≤n≤1e12。

數學模型

總蠟燭數 S = c + Σ_{i=1}^r k^i，其中 c∈{0,1}。等比數列求和 Σ k^i = k(k^r-1)/(k-1)。枚舉 r（最大約 40），對每個 r 二分 k 滿足 S=n 或 n-1。記錄最優 r,k。

核心代碼

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
using namespace std;
typedef long long ll;
ll n;
ll check(ll r){
    ll l=2, rgt=n, mid;
    while(l<=rgt){
        mid=(l+rgt)/2;
        ll sum=1, p=1;
        for(int i=1;i<=r;++i){
            if(n/p < mid){ sum=n+1; break; } // 溢出保護
            p*=mid;
            sum+=p;
            if(sum>n) break;
        }
        if(sum==n || sum==n-1) return mid;
        else if(sum < n-1) l=mid+1;
        else rgt=mid-1;
    }
    return -1;
}
int main(){
    while(scanf("%lld",&n)!=EOF){
        ll bestR=1, bestK=n-1;
        for(int r=2;r<=45;++r){
            ll k=check(r);
            if(k!=-1 && r*k < bestR*bestK){
                bestR=r; bestK=k;
            }
        }
        printf("%lld %lld\n",bestR,bestK);
    }
    return 0;
}

複雜度

枚舉 r≤45，每次二分 O(log n)，內層求和 O(r)，總時間 O(45 * log n * 45) 極快。