rockdu
莫比乌斯函数，由德国数学家和天文学家莫比乌斯提出。梅滕斯(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
杜教筛积性函数前缀和的裸题。杜教筛可以看唐教这一篇黑科技博客：“浅”谈一类积性函数求和
#include<cstdio>
#include<cmath>
#include<cstring>
#include<tr1/unordered_map>
#define LL long long
using namespace std;
using namespace tr1;
const int maxn = 5e6 + 5;
int pri[maxn], miu[maxn], M[maxn];
unordered_map<LL, LL> hsh;
LL a, b, N;
bool vis[maxn];
void prime(int N) {
M[1] = miu[1] = 1;
for(register int i = 2; i <= N; ++i) {
if(!vis[i]) pri[++pri[0]] = i, miu[i] = -1;
for(register int j = 1; j <= pri[0] && i * pri[j] <= N; ++j) {
vis[i * pri[j]] = 1;
miu[i * pri[j]] = miu[i] * miu[pri[j]];
if(i % pri[j] == 0) {
miu[i * pri[j]] = 0;
break;
}
}
M[i] = M[i - 1] + miu[i];
}
}
LL GetMiu(LL x) {
if(x <= N) return M[x];
if(hsh[x]) return hsh[x];
LL ret = 1, l = 2, r = 1, a;
while(r < x) {
l = r + 1, r = x / (x / l);
a = GetMiu(x / l), ret -= (r - l + 1) * a;
hsh[x / l] = a;
}
return ret;
}
int main() {
scanf("%lld%lld", &a, &b);
N = (LL)pow(b, 2.0 / 3.0) + 100;
prime((int)(N));
printf("%lld", GetMiu(b) - GetMiu(a - 1));
return 0;
}
没有帐号? 立即注册