徐老师的大富翁

文件读写

• 输入文件dice.in
• 输出文件dice.out

限制

• 1000ms
• 512MB

题目描述

徐老师最近很喜欢玩《大富翁》

在他玩的这款游戏里，有 $2$ 种特殊的骰子——指定骰子 和 倍数骰子

• 指定骰子：可以向前移动 $1 \sim k$ 步，具体移动步数由玩家指定，假设当前位置为 $x$ 号点，可以达到 $x+1 \sim x+k$ 中的任何一个位置
• 倍数骰子：假设当前位置为 $x$ 号点，可以直达 $x * p$ 号点，其中 $p$是游戏中固定的一个数值

玩家们的任务则是从 $1$ 号点出发，移动到 $E$ 号点结束，注意这里玩家必须是刚好站在 $E$ 号点才能获胜，如果超过了则游戏失败

现在徐老师想知道，他如果可以无限使用这两种骰子，最少需要使用几次骰子可以获胜？

输入格式

输入包含三个整数 $k,p,E$ 含义如题

输出格式

输出一个整数表示最少的使用次数

数据范围

对于 $20\%$ 的数据满足 $E \leq 1000$

对于 $40\%$ 的数据满足 $E \leq 10^5$

对于另外 $20\%$ 的独立数据满足 $E \leq 10^{18}, k \leq 1000, p = 1$

对于 $100\%$ 的数据满足 $E \leq 10^{18}, 1 \leq k \leq p \leq 1000$

样例输入1

1 2 8

样例输出1

3

样例解释1

一种方案为：$1->2->4->8$

样例输入2

1 2 10

样例输出2

4

样例解释2

一种方案为：$1->2->4->5->10$

样例输入3

1 2 123

样例输出3

11