[51NOD1239] 欧拉函数之和

题目

题目链接,求欧拉函数之和。
 

思路 1

首先的思路是和 51NOD1244 的推导过程是一样的。知 n = \sum_{d|n} \phi(d). 另 M(n) = \sum_{i=1}^{n} \phi(i)\sum_{i=1}^{n}i = \sum_{i=1}^{n} \sum_{d|i} \phi(d)\frac{n(n+1)}{2} =  \sum_{i=1}^{n} \sum_{d|i} \phi(d), 考虑 \phi(d) 的贡献,有 \frac{n(n+1)}{2} =  \sum_{i=1}^{n} \sum_{j = 1}^{\lfloor \frac{n}{i} \rfloor} \phi(j). 即 \frac{n(n+1)}{2} =  \sum_{i=1}^{n} M(\lfloor \frac{n}{i} \rfloor), 移项得 M(n) = \frac{n(n+1)}{2} -  \sum_{i=2}^{n} M(\lfloor \frac{n}{i} \rfloor).
分块记忆化递归处理即可。
 

代码

 

思路 2

可以看成 [1,n] 内有多少对数互质,另有小公约数为 x 的对数为 M(x),则有 M(x) = (\lfloor \frac{n}{x} \rfloor)^2.可以发现,答案是他们互相加减,而容斥的系数恰恰就是莫比乌斯函数,所以答案为 \sum_{i=1}^{n} \mu(i) M(x), 我们发现 M(x) 在一个区间内是相等的,而莫比乌斯函数的区间和可见 51NOD1244。 最后答案加一除二即可去重(模意义)。
 

代码

 

完结

发表评论

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