lstqwq 的题解说的复杂度错了吧，应该还要带上一个 $\gcd$ 的 $\log$，所以实际是 $n\log^3n$ 的。