CodeForces 165B Burning Midnight Oil

最新推荐文章于 2020-07-20 10:11:29 发布

追逐星辰的光

最新推荐文章于 2020-07-20 10:11:29 发布

阅读量291

点赞数

分类专栏：二分文章标签：二分

本文链接：https://blog.csdn.net/CS33sun/article/details/79160428

版权

二分专栏收录该内容

22 篇文章

订阅专栏

One day a highly important task was commissioned to Vasya — writing a program in a night. The program consists of n lines of code. Vasya is already exhausted, so he works like that: first he writes v lines of code, drinks a cup of tea, then he writes as much as $\text{[math]}$ lines, drinks another cup of tea, then he writes $\text{[math]}$ lines and so on: $\text{[math]}$ , $\text{[math]}$ , $\text{[math]}$ , ...

The expression $\text{[math]}$ is regarded as the integral part from dividing number a by number b.

The moment the current value $\text{[math]}$ equals 0, Vasya immediately falls asleep and he wakes up only in the morning, when the program should already be finished.

Vasya is wondering, what minimum allowable value v can take to let him write not less than n lines of code before he falls asleep.

Input

The input consists of two integers n and k, separated by spaces — the size of the program in lines and the productivity reduction coefficient, 1 ≤ n ≤ 10⁹, 2 ≤ k ≤ 10.

Output

Print the only integer — the minimum value of v that lets Vasya write the program in one night.

Example

Input

7 2

Output

Input

59 9

Output

Note

In the first sample the answer is v = 4. Vasya writes the code in the following portions: first 4 lines, then 2, then 1, and then Vasya falls asleep. Thus, he manages to write 4 + 2 + 1 = 7 lines in a night and complete the task.

In the second sample the answer is v = 54. Vasya writes the code in the following portions: 54, 6. The total sum is 54 + 6 = 60, that's even more than n = 59.

题意：给你两个数n,k，问满足： v + $\text{[math]}$ + $\text{[math]}$ + $\text{[math]}$ ... >= n 这个式子，求v的最小值。直接二分吧。

#include <stdio.h>
int solve(int x, int k) { //结果 
	int sum = x;
	while(x) {
		sum += (x/k);
		x = x/k;
	}
	return sum;
}
int main() {
	int n, k;
	int ans;
	while(~scanf("%d %d", &n, &k)) {
		int l = 1, r = n, m;
		while(l <= r) {
			m = l-(l-r)/2;
			int M = solve(m, k);
			if(M >= n) {
				ans = m;
				r = m-1;
			}
			else l = m+1;
		}
		printf("%d\n", ans);
	}
	return 0;
}