[51NOD1244] 莫比乌斯函数之和

题意

题目链接 51nod 1244, 大意为求 \sum_{i=a} ^ {b} \mu (i).
 

思路

首先我们习惯性把求区间和问题改成求前缀和,即求 M(n) = \sum_{i=1} ^ {a} \mu (i).
我们知道 \sum_{d|i} \mu (d) 只有在 i = 1 的情况下值为 1, 否则为 0.
所以有 1 = \sum_{i=1}^{n} \sum_{d|i} \mu (d).
我们换一个角度去考虑,考虑 \mu(d) 的贡献,因为 i = kd \mu(i/k)\mu (d) 会被计入贡献,所以当 k 值固定时,要被计入一次的函数值为 \mu(k / k), \mu(2k / k)....\mu(jk / k) 其中 j = \lfloor \frac{n}{k} \rfloor .
所以 1 = \sum_{i=1}^{n} \sum_{d|i} \mu (d) = \sum_{k=1}^{n} \sum_{i = 1} ^ {\lfloor  \frac{n}{k} \rfloor } \mu (i)1 = \sum_{k=1}^{n} M(\lfloor  \frac{n}{k} \rfloor )
k = 1 的那一项移除即得 M(n) = 1 - \sum_{k=2}^{n} M(\lfloor  \frac{n}{k} \rfloor ).
但是此时 n 还是很大,所以我们可以分块处理,对于小于 5000000 的部分用线性筛做,大于的部分递归加上记忆化处理。
在递归计算时我们发现,在 k \in [l, l / (n / l)] (整除) 这个区间里, \lfloor  \frac{n}{k} \rfloor 的值是相等的,所以这里也是一个可以优化的地方。
 

代码

 

完结

发表评论

电子邮件地址不会被公开。 必填项已用*标注