P2303 [SDOI2012] Longge 的问题

这一道题我的式子是：$\sum_{d\mid n} \lfloor \frac{n}{d} \rfloor \varphi(d)$

枚举d的时间复杂度是 $O(\sqrt n)$，求 $\varphi(d)$ 的时间复杂度也是 $O(\sqrt n)$,那这条式子复杂度是 $O(n)$吗？？？，可是 $O(n)$ 过不了啊！