文章目录
R
e
s
u
l
t
Result
Result
H
y
p
e
r
l
i
n
k
Hyperlink
Hyperlink
D
e
s
c
r
i
p
t
i
o
n
Description
Description
S
o
l
u
t
i
o
n
Solution
Solution
C
o
d
e
Code
Code
R
e
s
u
l
t
Result
Result
H
y
p
e
r
l
i
n
k
Hyperlink
Hyperlink
https://ac.nowcoder.com/acm/contest/7607/A
D
e
s
c
r
i
p
t
i
o
n
Description
Description
设
f
(
x
)
f(x)
f(x)表示
x
x
x除了1以外的所有因数的
g
c
d
gcd
gcd,求
∑
i
=
a
b
f
(
x
)
\sum _{i=a}^b f(x)
∑i=abf(x) 数据范围:
1
<
a
<
b
≤
1
0
7
1<a<b\leq 10^7
1<a<b≤107
S
o
l
u
t
i
o
n
Solution
Solution
设
s
i
=
∑
j
=
1
i
f
(
i
)
s_i=\sum_{j=1}^i f(i)
si=∑j=1if(i),则
A
n
s
=
s
b
−
s
a
−
1
Ans=s_b-s_{a-1}
Ans=sb−sa−1 考虑如何求
f
f
f,再做前缀和
当
x
x
x为质数时,
f
(
x
)
=
x
f(x)=x
f(x)=x 当
x
x
x的质因子只有一个质数时,则
f
(
x
)
f(x)
f(x)就等于它的最小质因子 否则
f
(
x
)
=
1
f(x)=1
f(x)=1
用线性筛处理上述过程,时间复杂度
O
(
m
a
x
{
a
,
b
}
)
O(max\{a,b\})
O(max{a,b})
C
o
d
e
Code
Code
#pragma GCC optimize(2)
%:pragma GCC
optimize(3)
%:pragma GCC
optimize("Ofast")
%:pragma GCC
optimize("inline")
#include<cctype>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
#define MAXN 10000010
using namespace std
;LL a
,b
,s
[MAXN
];
int prime
[MAXN
],m
,vis
[MAXN
],tot
;
inline LL
read()
{
char c
;LL d
=1,f
=0;
while(c
=getchar(),!isdigit(c
)) if(c
=='-') d
=-1;f
=(f
<<3)+(f
<<1)+c
-48;
while(c
=getchar(),isdigit(c
)) f
=(f
<<3)+(f
<<1)+c
-48;
return d
*f
;
}
inline void prework(LL N
)
{
for(register int i
=2;i
<=N
;i
++)
{
if(vis
[i
]==0)
{
s
[i
]=vis
[i
]=i
;prime
[++m
]=i
;
}
for(register int j
=1;j
<=m
&&prime
[j
]*i
<=N
;j
++)
{
if(prime
[j
]>vis
[i
]) break;
vis
[i
*prime
[j
]]=prime
[j
];
if(!s
[i
*prime
[j
]])
{
if(s
[i
]==1||s
[prime
[j
]]==1) {s
[i
*prime
[j
]]=1;continue;}
if(vis
[i
]==vis
[prime
[j
]]) s
[i
*prime
[j
]]=vis
[i
];
else s
[i
*prime
[j
]]=1;
}
}
}
for(register int i
=1;i
<=N
;i
++) s
[i
]+=s
[i
-1];
return;
}
signed main()
{
a
=read();b
=read();
prework(max(a
,b
));
printf("%lld",s
[b
]-s
[a
-1]);
}