← 返回题目列表

Codeforces · 251/C

C. 数字转换

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

小Petya非常喜欢正整数。最近他妈妈给了他一个正整数a。除了数字之外,佩蒂亚只喜欢一件事:和小玛莎一起玩。原来Masha已经有一个正整数b了。 Petya决定将他的数字a变成数字b,连续执行以下两种操作:

1.把他的号码减1。
2. 选择 2 到 k(含)之间的任意整数 x。然后从他的数字a中减去数字(a mod x)。运算 a mod x 表示取数字 a 除以数字 x 的余数。

Petya 每秒执行一次操作。每次他选择在当前移动期间执行的操作,无论当时他执行了哪种操作。特别是,这意味着他可以连续执行相同的操作任意次。

现在他想知道最少需要多少秒才能将数字 a 转换为数字 b。请注意,第二类运算中的数字x每次都会重新选择,彼此独立。

输入

唯一一行包含三个整数 a、b (1 ≤ b ≤ a ≤ 1018) 和 k (2 ≤ k ≤ 15)。

请不要使用 %lld 说明符在 С++ 中读取或写入 64 位整数。最好使用 cin、cout 流或 %I64d 说明符。

输出

打印一个整数 — 将数字 a 转换为数字 b 所需的最短秒数。

示例

输入 #1

10 1 4

输出 #1

6

输入 #2

6 3 10

输出 #2

2

输入 #3

1000000000000000000 1 3

输出 #3

666666666666666667

注意

在第一个样本中,Petya 在尝试获取数字 b 时获得的数字序列如下:10 → 8 → 6 → 4 → 3 → 2 → 1。

在第二个示例中,可能的序列之一如下:6 → 4 → 3。