Directly implementing the operation in the problem statement may exceed the execution time limit when \(A=10^{18}\) and \(B=1\), so it needs an improvement.

Here, consider the following algorithm, where we swap \(A\) and \(B\) if needed so that \(A > B\).

• Repeat the following until \(B=0\).
  • Add \(\lfloor \frac{A}{B} \rfloor\) to the answer and replace \(A\) with \(A \bmod B\).
  • Swap \(A\) and \(B\).
• Finally, subtract one from the answer.

This algorithm perform a bulk operation on \(A\) and \(B\) while the order of \(A\) and \(B\) is maintained, so the algorithm above works correctly. We finally subtract one because one excessive operation is performed after \(A=B\).

Now we consider the complexity of the algorithm above. We can see that replacing \(A\) with \(A \bmod B\) makes \(A\) less than half of the original value.

Thus, the complexity of the algorithm above is \(\mathrm{O}(\log A + \log B)\), which is fast enough.

Sample code (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;
}