直接反演？是 $O(d^2(n))$ 级别的。容易计算出 $k|\gcd(i,n)$ 的 $y^i$（也就是 $\sum_{k|i}y^i$）然后直接容斥？
by Daniel_lele @ 2023-01-31 09:02:43
@[Daniel_lele](/user/116664) 蒟蒻求问如何容斥，是否要算出 k 两两之间商的质数个数？
by peaneevall_kalaa @ 2023-01-31 09:08:56
@[zhouershan](/user/615348) 是的吧，商的莫比乌斯函数。
by Daniel_lele @ 2023-01-31 09:10:11
@[Daniel_lele](/user/116664) 谢谢
by peaneevall_kalaa @ 2023-01-31 09:12:24