因为 x=gcd(x,y) 使用辗转相除的复杂度是 log x-log(x,y)，所以对一个数执行 k 次此操作的总复杂度应该是 $O(k+\log x)$，因此第一篇题解的时间复杂度应当是 $O(n(\log A_i+\log n))$。