是不是辗转相除复杂度反而有问题啊

反辟谣

设 $n$ 为数的大小，进制数是常数，则位数是 $O(\log n)$ 的，朴素高精度除法就是 $O(\log^2n)$ 的了，求 GCD 的时候需要除 $O(\log n)$ 次，总复杂度就是 $O(\log^3n)$ 了

而高精度减法和高精除 $2$ 复杂度都是 $O(\log n)$ 的，而有人已经证明了带除 $2$ 的更相减损术操作次数是 $O(\log n)$ 了，总复杂度就是 $O(\log^2n)$ 了。

不把进制数当成常数也一样，高精度除法无论如何都会比高精度减法复杂度高一些，而操作次数复杂度一样，所以辗转相除的算法复杂度是比更相减损术差的。

（说实话当时我小奥老师让我们求 GCD 的时候就教过这个方法，不要相除（因为容易出错而且计算量大），而是相减然后约掉一些明显不在 GCD 中的因数）