← 返回题目列表

Codeforces · 165/B

B. 午夜燃烧的油

中文机器翻译题面 查看原题

有一天,Vasya 被委托执行一项非常重要的任务——在一个晚上编写一个程序。该程序由n行代码组成。 Vasya 已经筋疲力尽了,所以他这样工作:先写 v 行代码,喝一杯茶,然后写 $$\left[\frac{v}{k}\right]$$ 行,再喝一杯茶,然后写 $$\left[\frac{v}{k^{2}}\right]$$ 行,依此类推:$$\left[\frac{v}{k^{3}}\right]$$, $$\left[\frac{v}{k^{4}}\right]$$, $$\left[\frac{v}{k^{5}}\right]$$, ...

表达式 $$\left[\frac{a}{b}\right]$$ 被视为数字 a 除以数字 b 的整数部分。

当前值$$\left[\frac{v}{k\cdot p}\right]$$等于0的那一刻,Vasya立即入睡,直到早上才醒来,此时程序应该已经完成​​了。

Vasya想知道,v的最小允许值可以取多少才能让他在睡着之前写出不少于n行代码。

输入

输入由两个整数 n 和 k 组成,以空格分隔 — 程序的行数和生产率降低系数,1 ≤ n ≤ 109, 2 ≤ k ≤ 10。

输出

打印唯一的整数——让 Vasya 一晚上写出程序的 v 的最小值。

示例

输入 #1

7 2

输出 #1

4

输入 #2

59 9

输出 #2

54

注意

在第一个示例中,答案是 v = 4。Vasya 按以下部分编写代码:前 4 行,然后是 2 行,然后是 1 行,然后 Vasya 睡着了。于是,他一晚上就写了4+2+1=7行,完成了任务。

在第二个示例中,答案是 v = 54。Vasya 将代码分为以下部分:54, 6。总和为 54 + 6 = 60,甚至比 n = 59 还要多。