=== ===
这里放传送门
=== ===
题解
首先题目给出的A函数实际上就是
1n∑i=1nn∗i(i,n)=∑i=1ni(i,n)
然后F函数就可以写成
∑i=1n∑j=1ij(i,j)
然后按照常用套路化一波式子就会变成
∑d=1n∑i=1⌊nd⌋∑j=1i[(i,j)==1]j
这个样子，后面那一块可以发现就是1..i中与i互质的数字的和，那就是
φ(n)∗n+[n==1]2
了。然后可以发现在
d
从1到n枚举的过程中总共有n次i==1的情况，也就是一共有n次加上了[n==1]这个条件。那么把这个n提出来，然后把那个除以2也刨掉先不看，式子就变成了
∑d=1n∑i=1⌊nd⌋φ(i)∗i
这个样子了。 这个式子显然看起来非常美好哇因为如果设
F(n)=φ(n)∗n
，只要能够求出F函数的前缀和就可以枚举除法根n分块了哇 然后又是杜教筛的问题了。。。 现在的问题变成了要求
∑i=1nφ(n)∗n
，用杜教筛。
首先要通过卷积构造一个等式
H=F×G
，其中
H
和G都是好求前缀和的函数。于是我们令
H=F×id=∑d|nφ(d)∗d∗(nd)
。选择id函数的原因就是它能够约掉那个d，然后就变成了
n∗∑d|nφ(d)
。后面那一坨是
φ×1
，也是个
id
，那就变成了
n∗n
，也就是
H(n)=n2
。 然后就是按照杜教筛的方法画柿子。。
Sum(n)=∑i=1ni2−∑d|i,d<iF(d)∗id=∑i=1n−∑i=1n∑d|i,d<iF(d)∗id
然后因为i必须是d的倍数但i不能等于d，也就是
id
不能等于1。那么枚举
id
就变成了：
∑i=1ni2−∑id=2n∑d=1⌊n⌊id⌋⌋F(d)∗id
然后设
i′=id
，替换一下就有：
∑i=1ni2−∑i=2n∑d=1⌊ni⌋F(d)∗did=∑i=1ni2−∑i=2ni∑d=1⌊ni⌋F(d)
那么后面就又出现了一段F函数的前缀和的形式，
i
的前缀和还有i2的前缀和都很好算，于是就可以用杜教筛解决这个问题了。
代码
#include<map>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const long long Mod=
1e9+
7;
const long long inv=
500000004;
const long long inv6=
166666668;
int a,b,prm[
5000010];
bool ext[
5000010];
long long ans,phi[
5000010];
map<long long,long long> rec;
void get_prime(
int N){
phi[
1]=
1;
for (
int i=
2;i<=N;i++){
if (ext[i]==
false){
prm[++prm[
0]]=i;phi[i]=i-
1;
}
for (
int j=
1;j<=prm[
0];j++){
if ((
long long)i*prm[j]>N)
break;
ext[i*prm[j]]=
true;
if (i%prm[j]==
0){
phi[i*prm[j]]=phi[i]*prm[j];
break;
}
else phi[i*prm[j]]=phi[i]*phi[prm[j]];
}
}
for (
int i=
1;i<=N;i++) phi[i]=phi[i]*i%Mod;
for (
int i=
1;i<=N;i++) phi[i]=(phi[i]+phi[i-
1])%Mod;
}
long long S(
long long l,
long long r){
long long s1=r*(r+
1)/
2;
long long s2=(l-
1)*l/
2;
return (s1-s2)%Mod;
}
long long Sumphi(
long long n){
if (n<=
5000000)
return phi[n];
if (rec[n]!=
0)
return rec[n];
long long sum=n*(n+
1)%Mod;
sum=sum*(
2*n+
1)%Mod;
sum=sum*inv6%Mod;
for (
long long i=
2,tail;i<=n;i=tail+
1){
tail=n/(n/i);
sum=(sum-S(i,tail)*Sumphi(n/i)%Mod)%Mod;
}
return rec[n]=sum;
}
long long Getans(
int n){
long long sum=
0;
for (
long long i=
1,tail;i<=n;i=tail+
1){
tail=n/(n/i);
sum=(sum+(tail-i+
1)*Sumphi(n/i)%Mod)%Mod;
}
return ((sum+n)*inv)%Mod;
}
int main()
{
get_prime(
5000000);
scanf(
"%d%d",&a,&b);
ans=(Getans(b)-Getans(a-
1))%Mod;
printf(
"%I64d\n",(ans+Mod)%Mod);
return 0;
}
