技術室奥プログラミングコンテスト#2

D - エンブレム(Emblem)


Time limit時間制限 : 1sec / Memory limitメモリ制限 : 64MB

問題文

joisinoお姉ちゃんの次の仕事は、デザイナーさんを助けることである。
今、あるエンブレムのデザインが行われている。
エンブレムは、以下の手順で作られる。

  • まず、縦H×横Wの大きさの長方形を用意する。
  • この時、左下の角を座標(0,0)とし、そこから右にx、上にy進んだ位置を座標(x,y)で表す。
  • 座標(0,0)から、座標(K,H) (1≦K<W,Kは整数)に向かい、直線を引き始める。
  • 以後、以下のような動作を続ける。
  • 直線がどこかの角にぶつかるならば、そこでデザインを終了する。
  • 直線が角でない端にぶつかるならば、そこで、入射角と反射角が等しくなるように反射する。
  • たとえば、H=3,W=5,K=2のとき、図のようなデザインが完成する。ここで、赤い線が引いた線であり、濃い緑の線は、長方形の大きさをわかりやすくするために書いてあるだけなので、デザインには関係ない。

    こうしてできたデザインの美しさは、長方形の内部にある線の交点の個数と等しい。例えば、上の図であれば、赤い線が交わる点が2箇所あるので、美しさは2である。
    デザイナーさんは、H,W,Kの候補を考えたが、実際に描く前に、それを元に作ったデザインの美しさを前もって知っておきたいと思った。
    joisinoお姉ちゃんの仕事は、H,W,Kが与えられたときに、それを元に作ったデザインの美しさを求めるプログラムを作ることである。


    入力

    入力は以下の形式で標準入力から与えられる。

    H W K
    
    • 1行目には、長方形の大きさを表す整数H(2 ≦ H ≦ 10^9),W(2 ≦ W ≦ 10^9)と、線を引く方向を示す整数K(1 ≦ K < W)が与えられる。

    出力

    与えられたH,W,Kを元に作ったデザインの美しさを1行に出力せよ。


    入力例1

    3 5 2
    

    出力例1

    2
    

    この入力は、問題文中の図と対応している。


    入力例2

    7 6 5
    

    出力例2

    10
    

    入力例3

    1000000000 1000000000 999999999
    

    出力例3

    499999998500000001
    

    Submit提出する