問題文の操作をそのまま実装すると、\(A=10^{18},B=1\) などのときに実行制限時間をオーバーしてしまいます。よって、何かしらの工夫が必要です。

ここで、以下のようにすることを考えます。ただし、始めに \(A > B\) になるように swap を行います。

• \(B=0\) になるまで以下を繰り返す。
  • 答えに \(\lfloor \frac{A}{B} \rfloor\) を足し、\(A\) を \(A \bmod B\) で置き換える。
  • \(A,B\) を swap する。
• 最後に答えから \(1\) を引く。

元の操作での \(A,B\) の大小関係が同じ操作を一度にまとめて行っているということなので、上記で答えは正しく求まります。最後に \(1\) を引くのは、\(A=B\) となったとき更に \(1\) 回多く操作をしてしまうからです。

上記のアルゴリズムの計算量を考えます。\(A\) を \(A \bmod B\) で置き換えると、\(A\) が元の半分未満になることが分かります。

よって、上記のアルゴリズムの計算量は \(\mathrm{O}(\log A + \log B)\) です。これは十分高速です。

実装例(C++)

#include<bits/stdc++.h>
using namespace std;
int main() {
  long long a,b;
  cin>>a>>b;
  long long ans=0;
  if(a<b) swap(a,b);
  while(b>0){
    ans+=a/b;
    a%=b;
    swap(a,b);
  }
  cout<<ans-1<<endl;
}