题目大意
求$\sum_{i=x}^y\mu(i)$。
题目分析
又一道杜教筛入门题。
为了下文描述方便，我们记$M(n)=\sum_{i=1}^n\mu(i)$。
根据众所周知的结论：
我们有：
预处理$n^\frac23$以内的$M(i)$，使用杜教筛递归计算。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
| #include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
typedef long long LL;
#define pii pair<LL,LL>
#define mp make_pair
inline const LL Get_Int() {
LL num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int limit=5000000;
const LL hashmod=999959;
bool vst[limit+5];
int cnt=0,Prime[limit+5],Mobius[limit+5];
vector<pii>Hash[hashmod+5];
void Table(int n) {
Mobius[1]=1;
for(int i=2; i<=n; i++) {
if(!vst[i]) {
Prime[++cnt]=i;
Mobius[i]=-1;
}
for(int j=1; j<=cnt&&i*Prime[j]<=n; j++) {
vst[i*Prime[j]]=1;
if(i%Prime[j]==0) {
Mobius[i*Prime[j]]=0;
break;
}
Mobius[i*Prime[j]]=-Mobius[i];
}
}
for(int i=2; i<=n; i++)Mobius[i]+=Mobius[i-1];
}
void Add(int x,LL p,LL v) {
Hash[x].push_back(mp(p,v));
}
LL Cal(LL n) {
if(n<=limit)return Mobius[n];
for(pii x:Hash[n%hashmod])if(x.first==n)return x.second;
LL Next,ans=0;
for(LL i=2; i<=n; i=Next+1) {
Next=n/(n/i);
ans+=(Next-i+1)*Cal(n/i);
}
ans=1-ans;
Add(n%hashmod,n,ans);
return ans;
}
int main() {
Table(limit);
LL x=Get_Int(),y=Get_Int();
printf("%lld\n",Cal(y)-Cal(x-1));
return 0;
}
|
