ABC297 D問題 Count Subtractions

正の整数 $A,B$ に対して
$A > B$ なら $A \to A - B$
$A < B$ なら $B \to B - A$
を何回繰り返すと $A = B$ になるかという問題です。

この操作を1回ずつ行うと、たとえば $A = 1, B = 10^{18}$ のとき $10^{18}$ 回程度になるため時間がかかりすぎます。

そこで、 $A > B$ の場合、 $A$ を $B$ で割った商 $d$ と余り $r$ を求めます。 $d$ 回の操作で、 $A \to A - d B = r$ になるので、
$r\ne 0$ であれば次に $r$ と $B (r < B)$ に対する操作を考えます。 $r=0$ であれば、 $d-1$ 回の操作後に $A-(d-1)B = B$ と等しくなります。

コード例 (Julia)

function solve()

  # 入力
  readInts() =  parse.(Int,split(readline()))
  readInt()  =  parse(Int,readline())

  A,B = readInts()

  if A < B
    A,B = B,A
  end

  ans = 0

  while A > B
    d,r = divrem(A,B)
    if r==0
      ans += d-1
      A -= (d-1)*B
    else
      ans += d
      A,B = B,A-d*B
    end
  end

  println(ans)

end  # function solve

# main
solve()