← 返回题目列表

AtCoder · code_festival_final_j

J. 2 杯

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

問題文

水 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