$$
\sum_{i=1}^n \varphi(d(i))=\sum_{x=1}^{k}\varphi(x)\sum_{i=1}^n [d(i)=x]
$$
$$
k=max_{i=1}^n d(i)
$$
后面那个暴力dfs，感觉应该行
by ricky0916 @ 2024-02-27 14:22:02
怎么求后面这个值?
by ZnPdCo @ 2024-02-27 14:35:56
@[ricky0916](/user/289230)
by ZnPdCo @ 2024-02-27 14:36:29
@[ZnPdCo](/user/560700) 好吧其实我是瞎说的。。。
但是用这个就行 [PN筛](https://oi-wiki.org/math/number-theory/powerful-number/) 然后 $ h(p^k)=\sum_{i=0}^k \varphi(i) (-1)^{k-i} $ 这个直接对每个k暴力预处理
~~刚学的~~
by ricky0916 @ 2024-02-27 15:18:56
还有那个 $g(x)=1$
by ricky0916 @ 2024-02-27 15:23:00
@[ricky0916](/user/289230) 感谢！
by ZnPdCo @ 2024-02-27 15:23:50