51nod 1244 莫比乌斯函数之和

51nod 1244 莫比乌斯函数之和

描述

莫比乌斯函数，由德国数学家和天文学家莫比乌斯提出。梅滕斯(Mertens)首先使用μ(n)（miu(n)）作为莫比乌斯函数的记号。具体定义如下：如果一个数包含平方因子，那么miu(n) = 0。例如：miu(4), miu(12), miu(18) = 0。如果一个数不包含平方因子，并且有k个不同的质因子，那么miu(n) = (-1)^k。例如：miu(2), miu(3), miu(30) = -1,miu(1), miu(6), miu(10) = 1。给出一个区间[a,b]，S(a,b) = miu(a) + miu(a + 1) + …… miu(b)。例如：S(3, 10) = miu(3) + miu(4) + miu(5) + miu(6) + miu(7) + miu(8) + miu(9) + miu(10) = -1 + 0 + -1 + 1 + -1 + 0 + 0 + 1 = -1。

Input

输入包括两个数a, b，中间用空格分隔(2 <= a <= b <= 10^10)

Output

输出S(a, b)。

Input示例

3 10

Output示例

-1

思路

对于区间和我们可以将其分解为两个前缀和的差

求 ∑ri=lμ(i)

我们设 M(n)=∑ni=1μ(i)

已知 ∑d|nμ(d)=[n=1] （当 n=1 时结果为 1 ，其余为 0

所以有 ∑ni=1∑d|iμ(d)=∑ni=1∑⌊ni⌋d=1μ(d)=∑ni=1M(⌊ni⌋)=1

因为 ∑ni=1M(⌊ni⌋)=M(n)+∑ni=2M(⌊ni⌋)=1

所以 M(n)=1−∑ni=2M(⌊ni⌋)

然后就可以根据这个式子递归得出结果咯~

需要注意时间上的优化：

因为 ⌊ni⌋记录已得出的结果，在之后遇到的时候直接使用预先处理出一段前缀和

AC 代码

#include#include#include#include#include#include#include#include

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。