\(A=B\) の時、答えは \(1\) です。以降、\(A \neq B\) とします。

\(\mathrm{gcd}(a,b) \neq 1\) の時、以降の操作中の \(a,b,g\) はすべて \(\mathrm{gcd}(a,b)\) の倍数となるため、 \(a,b\) を \(\frac{a}{\mathrm{gcd}(a,b)}, \frac{b}{\mathrm{gcd}(a,b)}\) に置き換えて、操作は \(a,b\) から \(1\) 引くものとしても構いません(必須ではありませんが、剰余の扱いが多少簡単になるので以降この前提で説明をします)。
\(\mathrm{gcd}(a-t, b-t) \neq 1\) となるような最小の \(t\) が分かれば操作をまとめて行うことが出来、高速化が見込めます。ここで、操作によって \(|a-b|\) は変わらないため、\(\mathrm{gcd}(a-t, b-t)\) としてあり得るのは \(|a-b|\) の約数に限ります。よって、\(|a-b|\) の \(2\) 以上の約数 \(x\) それぞれに対する \(a \bmod x\) の最小値が \(t\) となります。

\(A,B\) を \(2\) 以上の値で割れる回数は \(\mathrm{O}(\log A)\) 回なので、上記解法の計算量は \(\max (A,B)\) を \(N\) として \(\mathrm{O}(\sqrt{N} \log N)\) です。また、\(|a-b|\) の約数の代わりに\(|A-B|\) の約数を考えるだけでも十分なため、\(|A-B|\) の約数の個数を \(d\) として \(\mathrm{O}(\sqrt{N} + d\log N)\) になる他、素因数のみを考えれば十分なので　\(|A-B|\) の素因数の個数を \(p\) として \(\mathrm{O}(\sqrt{N} + p\log N)\) とすることも出来ます。