那么： $$ \begin{align} ans&=\sum_{d|n}f(d)h(d)\\ &=\sum_{d|n}h(d)\sum_{p|d}\mu(\frac dp)g(p)\\ &=\sum_{p|n}g(p)\sum_{p|d,d|n}h(d)\mu(\frac dp)\\ &=\sum_{p|n}g(p)\sum_{d|\frac np}h(dp)\mu(d)\\ \end{align} $$ 发现 $h(dp)$ 很不好处理，我们考虑能否把 $d$ 提出来，即什么时候 $h(dp)=dh(p)$ ，讨论一下可以发现只有当 $d$ 为偶数 $p$ 为奇数的时候 $h(dp)=\frac{dp}2\ne dh(p)$ ，但是这个时候一定满足 $\frac pn$ 为偶数，那么我们可以把所有奇数和偶数按 $d-2d$ 这样配对，由于后面有一个莫比乌斯函数因此 $2$ 的幂次不超过 $1$ ，然后会发现： $$ h(dp)\mu(d)=dp\mu(d)\\h(2dp)\mu(2d)=dp-mu(d) $$ 也就是说如果存在这种情况整个后面那个和式答案都是 $0$ ，因此我们可以直接操作： $$ \begin{align} ans&=\sum_{p|n}g(p)\sum_{d|\frac np}h(dp)\mu(d)\\ &=\sum_{p|n}g(p)\sum_{d|\frac np}dh(p)\mu(d)\\ &=\sum_{p|n}g(p)h(p)\sum_{d|\frac np}d\mu(d)\\ &=\sum_{p|n}g(p)h(p)w(\frac np)\\ &=\sum_{p|n}g(\frac np)h(\frac np)w(p)\\ \end{align} $$ 最难求的显然是 $w(x)$ ，把质数的幂拆开之后就可以发现： $$ w(x)=\prod_{i}(1-p_i) $$ 于是 $pollard-rho$ 分解一下素因子，然后 $dfs$ 枚举 $p$ 就行了。