B. Burning Midnight Oil

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

Felven

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

阅读量1.3k

点赞数

分类专栏： AC路漫漫

本文为博主原创文章，未经博主允许不得转载。

本文链接：https://blog.csdn.net/zhaoxinfan/article/details/9631443

版权

AC路漫漫专栏收录该内容

1828 篇文章

订阅专栏

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 ≤ 109, 2 ≤ k ≤ 10.

Output

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

       Sample test(s) 
     
         input 
       
7 2

         output 
       
4

         input 
       
59 9

         output 
       
54

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.

解题说明：利用二分搜索，属于找下界的题目，需要注意两种情况：

1. 当n<k的时候直接输出n即可，

2. 当n特别大的时候计算出来的sum值以及k^p的结果可能会超出int范围故需要用long long 保存。

#include <cstdio>
#include<iostream>
using namespace std;

int main()
{
	int n, k, v, i, sum;
	scanf("%d%d", &n, &k);
	v = n / k * (k - 1);
	do
	{
		sum = 0;
		i = 1;
		while (v / i > 0)
		{
			sum += v / i;
			i *= k;
		}
		if (sum < n)
		{
			++v;
		}
		else
		{
			break;
		}
	}
	while (1);
	printf("%d\n", v);
	return 0;
}