题目
传送门
题目描述
我们定义
f
(
x
)
=
g
c
d
f(x) = gcd
f(x)=gcd
(
x
(x
(x除
1
1
1之外的所有因子
)
)
) 即
x
x
x除
1
1
1外所有因子的
g
c
d
gcd
gcd 询问从
f
(
a
)
+
f
(
a
+
1
)
+
…
…
+
f
(
b
)
f(a) + f(a+1) + …… + f(b)
f(a)+f(a+1)+……+f(b)
输入描述
输入两个正整数
a
，
b
a，b
a，b
输出描述
输出一个正整数表示答案
分析
不难找到如下规律：
若
x
x
x是质数，则
g
c
d
(
x
)
=
x
gcd(x)=x
gcd(x)=x若
x
x
x是
k
k
k的正整数次幂（
k
k
k为质数），则
g
c
d
(
x
)
=
k
gcd(x)=k
gcd(x)=k若
x
x
x有两个及以上的质因数，则
g
c
d
(
x
)
=
1
gcd(x)=1
gcd(x)=1
于是很自然的，先把数据范围内所有质数筛一遍，然后用筛出来的质数对区间内每一个数进行操作即可 注意答案为
l
o
n
g
long
long
l
o
n
g
long
long
代码
#include <bits/stdc++.h>
#define ll long long
using namespace std
;
const int maxn
=1e7;
int l
,r
,num
,P
[maxn
];ll ans
;
bool isP
[maxn
];
void Pr()
{
for(int i
=2;i
<=maxn
;i
++)
{
if(isP
[i
]) continue;P
[++num
]=i
;
for(int j
=i
+i
;j
<=maxn
;j
+=i
) isP
[j
]=1;
}
}
int main()
{
Pr();
scanf("%d%d",&l
,&r
);
for(int i
=l
;i
<=r
;i
++)
{
if(!isP
[i
])
{
ans
+=1ll*i
;
continue;
}int ii
=i
;
for(int j
=1;j
<=num
&&P
[j
]<=ii
;j
++)
{
if(ii
%P
[j
]==0)
{
while(ii
%P
[j
]==0) ii
/=P
[j
];
if(ii
==1) ans
+=1ll*P
[j
];
else ans
+=1ll;
break;
}
}
}
printf("%lld",ans
);
}
----原创文章，仅供参考
