警示：如果你的代码出奇的慢

枚举 $[1,\varphi(n)]$ 中每个数与 $\varphi(n)$ 的 $\gcd$ 的时候，要使用 $O(n)$ 的线性筛，而非 $O(n\log n)$ 的暴力手动求解。

如果你使用了后者，会导致其成为代码的时间复杂度瓶颈（代码的其他部分如果实现正确的话时间复杂度应该都不会超过 $O(n)$），使性能大幅降低。