题解

思路

若 $A=B$，一次操作后两数都变成零。

做法

否则先除以 $\gcd(A,B)$；这不会改变操作次数，此后每轮都可在除去当前 gcd 后看成同时减一。两数之差在减法中不变，只会在约去 gcd 时缩小，所以能够让下一次 gcd 变大的质因子一定来自初始差 $|A-B|$。先分解这个差并保留不同质因子；在当前两数互质时，对仍整除当前差的每个质因子 $p$，两数模 $p$ 的余数相同，取这些余数与较小数的最小值 $t$，即可安全地一次累计 $t$ 次操作。减去 $t$ 后若两数仍为正，就约去新的 gcd 并继续。

复杂度

每轮至少约去一个不小于 $2$ 的因子，因此轮数为 $O(\log N)$；总时间复杂度为 $O(\sqrt N+p\log N)$，其中 $p$ 是初始差的不同质因子数，空间复杂度为 $O(p)$。