以题目 “HDU - 2204 Eddy’s爱好” 为例
首先比较容易想到的是对于一个 [1,n] 这 n 个数，可以写成 ax 的一共有 n1x 个数字。
那么首先我们可以枚举 x ，就能完全不遗漏地考虑到所有满足情况的数字。但是，这之间一定会有数字重复考虑了，比如：如果一个数可以表示成 a12 那么它就一定可以表示成 a6 ；如果一个数可以表示成 a6 ，那么它一定既可以表示成 a2 也同样可以表示成 a3 。
那么首先为了方便计数，我们把 x 表示成：
x=pc11pc22...pckk
如果
c1,c2...ck 不都为1，那么我们直接不记录它的贡献了，因为它可以唯一确定的对应成
x′=p1p2...pk ，即
c1,c2...ck 都为 1 的情况，它的贡献就看成
x′ 的贡献就完了。然后就是如果
x 只由若干质数相乘得到的情况了，设：
x1=p1∗p2...pk∗gcd(x1,x2) ，
x2=q1∗q2...qk∗gcd(x1,x2) 那么
x1 和
x2 贡献重复的部分即为：
lcm(x1,x2) 的贡献。
所以容斥一下就是：
x 对总答案的贡献为
(−1)k+1∗n1x ，我们容易发现，如果设
f(x)=n1x ，那么贡献就是：
(−1)k+1∗f(x) ，这就恰好符合了莫比乌斯函数
u(x) 的定义。所以我们得到最终答案：
ans=∑i=1nu(i)∗(f(i)−1)
京公网安备 11010502036488号