問題文
水 A 一升杯子和水 B 一个可以容纳升的杯子 每个都有 1 。
从一个空杯子开始,重复以下操作之一,将其中一个杯子装满水。 C 我希望能够存储升。
- 将一杯水装满。
- 空一个杯子。
- 一杯 X 来自另一个杯子 Y 到, Y 会满吗? 排出水,不要溢出,直到 X 变空。 给出了
A, B, K ,所以 K 几次操作即可实现不同的方法。 找出有多少种方式 C 。
入力
输入将以以下格式从标准输入提供。
A B K
- 1 行包含一个表示杯子容量的整数。 A,B (1 ≦ A, B ≦ 10^{10}) 和一个表示可能操作数的整数 K (0 ≦ K ≦ 10^{10}) 。
出力
可以实现的不同事情 找出有多少种方式 C 。在输出末尾添加换行符。
入力例1
3 4 2
出力例1
4
首先, 如果 0 在初始状态下实现。
3 和 4 将每个容量杯装满水, 它可以通过 1 操作来实现。
1 是容量 向 4 杯中加水,直至其容量耗尽 转移到 3 杯, 这可以通过2 操作来实现。
2 是 代表第2 一次操作无法实现, 需要进行 4 操作。
入力例2
7 3 0
出力例2
1
由于它不可操作,所以它是空的,即 0 只能实现。
入力例3
174324 96581 5000
出力例3
3220