$n \le 10^9$。

对 $n$ 的每个因数求一遍欧拉函数，本蒟蒻不会分析复杂度。

写一道题的时候原以为会 T 飞，没想到过了。。。。而且是 0ms。