RT，赛时不会做 C 急急急，瞎猜结论过了，但至今没证出来为什么是对的。

做法大概是：每次暴力找 $n$ 的最大质因子 $x$，并令 $n-=n/x$。

时间复杂度/正确性都不会证，求助 /kel