题意:按照每一圈的蜡烛数量为k^i(1<= i <= r)摆放蜡烛,求r*k最小时的r和k注意,中心可以摆蜡烛也可以不摆蜡烛
题解:这是一道二分的题目,在求解过程中,先可以根据等比数列求和公式以及数据范围得出,蜡烛最多有40圈,所以求解r*k的最优解可以通过从2到40枚举半径r,并通过半径r去二分计算该半径下,如果存在蜡烛根数的解,那么解k是多少。
#include <stdio.h>
#include <iostream>
using namespace std ;
long long tot ;
long long judge(long long s)
{long long l = 2 , r = tot - 1 , mid ,sum ,ans;while(l <= r){mid = (l + r)/2 ;sum = 1 ;ans = 0 ;for(int i = 1 ; i <= s ; i ++){if(tot/sum < mid)//可行性剪枝{ans = tot + 1 ;break ;}sum *= mid ;ans += sum ;if(ans > tot) break ;}if(ans == tot-1 || ans == tot) return mid ;else if(ans < tot-1) l = mid + 1 ;//如果解答比总数少,则说明k取小了else r = mid - 1 ;}return -1 ;
}
int main()
{long long k ;while(scanf("%I64d" , &tot)!= EOF ){long long low , high , flag;low = 1 ;high = tot-1 ;for(k = 2 ; k <= 42 ; k ++){flag = judge(k) ;if(flag != -1 && k * flag < low * high){low = k ;high = flag ;}}printf("%I64d %I64d\n", low , high);}return 0 ;
}