J - 2つのカップ
解説
/
実行時間制限: 2 sec / メモリ制限: 256 MB
問題文
水が 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