2つのカップ

## 题目描述 现在有两个杯子，容量分别为A升和B升。 初始状态下，它们都是空的。现在给出几种操作，你需要让一个杯子里有C升水。 1.把一个杯子装满水。 2.把一个杯子倒空。 3.将一个杯子里的水全部倒入另一个杯子里。 现在给出A、B、K，请问在K个操作之内能得到多少个不同的C。

[problemUrl]: https://atcoder.jp/contests/code-festival-2014-final/tasks/code_festival_final_j 水が $ 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 $ は何通りあるかを求めよ。出力の最後には改行を入れること。

3 4 2

4

7 3 0

1

174324 96581 5000

3220

### Sample Explanation 1 まず、 $ 0 $ は初期状態で実現されています。 $ 3 $ および $ 4 $ は、それぞれの容量のカップの水を満たす、 $ 1 $ 回の操作で達成可能です。 $ 1 $ は、 容量 $ 4 $ のカップに入れた水を、空になっている容量 $ 3 $ のカップに移す、$ 2 $ 回の操作で実現できます。 $ 2 $ は、$ 2 $ 回の操作で実現することは出来ず、 $ 4 $ 回の操作が必要となります。 ### Sample Explanation 2 操作不可能なので、空の状態、つまり $ 0 $ のみを実現することしかできません。