萌新说一下关于这题的复杂度

ouuan 的上一个帖子里谈到了这个问题。

即题解里说单次复杂度是 $O(\sqrt[4] {n^3})$ 。

原因可能是因为他们默认了每次循环都会进入求\phi的环节，而每次求\phi的平均复杂度是 $O(\sqrt{\sqrt n})$，这个平均复杂度是因为每当存在一个 $>\sqrt n$ 的因子必然会存在一个 $<\sqrt n$ 的因子，所以这显然有一个上界是 $\frac{3}{4}$。

但是如果按照 $O(d(n)\cdot \sqrt{ \sqrt{n}})$ 来分析，那么一定不会超过 $O(n^{\frac{1}{4}+\frac{1}{3}}=n^{\frac{7}{12}})$ 。这个因子数量是毛子估出来的一个比较松的上界。然而这个还是很松，因为 $\sqrt n$ 的变化率极小，所以 $\sqrt{ \sqrt{n}}$ 是很松的。

所以这大概就是能够 $1s$ 内过掉这题的原因。可以发现当 $n=10^9$ 时最终多组数据总运算量大概在 $10^8$ 左右，是一个比较常见可以过掉的数据范围。