反辟谣
设 n 为数的大小,进制数是常数,则位数是 O(logn) 的,朴素高精度除法就是 O(log2n) 的了,求 GCD 的时候需要除 O(logn) 次,总复杂度就是 O(log3n) 了
而高精度减法和高精除 2 复杂度都是 O(logn) 的,而有人已经证明了带除 2 的更相减损术操作次数是 O(logn) 了,总复杂度就是 O(log2n) 了。
不把进制数当成常数也一样,高精度除法无论如何都会比高精度减法复杂度高一些,而操作次数复杂度一样,所以辗转相除的算法复杂度是比更相减损术差的。
(说实话当时我小奥老师让我们求 GCD 的时候就教过这个方法,不要相除(因为容易出错而且计算量大),而是相减然后约掉一些明显不在 GCD 中的因数)