TOJ 4373 HDU 4430 ZOJ 3665 Yukari's Birthday / 二分
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 placen 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 liker ≥ 1 concentric circles. They place ki candles equidistantly on thei-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 ofr and k satisfying these restrictions, they want to minimizer × k. If there is still a tie, minimize r. There are about 10,000 test cases. Process to the end of file. Each test consists of only an integer 18 ≤ n ≤ 1012. For each test case, output r and k. #include <stdio.h>const long long MAX = 1000010;long long n;long long check(long long k,long long r){long long res = 0,i,m = k;for(i = 1;i <= r; i++){res += m;//printf("%I64d\n",res);m *= k;if(res > n)return MAX * MAX;}return res;}long long erfen(long long l,long long r,long long k){if(k == 1)return n - 1;while(l <= r){long long m = (l + r) >> 1;long long res = check(m,k);//printf("%I64d\n",res);if(res == n || res == n - 1)return m;if(res > n)r = m - 1;elsel = m + 1;}return -1;}int main(){long long l,r,i,R,K,RR,KK;while(scanf("%lld",&n)!=EOF){RR = MAX;KK = MAX;for(i = 1;i <= 40; i++){l = 2;r = 1000000;long long res = erfen(l,r,i);if(res != -1){if(res * i < RR * KK || res * i == RR * KK && i < RR){RR = i;KK = res;}}}printf("%lld %lld\n",RR,KK);}return 0;}
