题意
求 ，其中
。
题目链接
题解
众所周知，。
这个应该是小学只是了吧，我就不证了。（虽然我也不会比较严谨的证明）
加入我们要求一段区间的和，其实只需要能够求前缀就可以了。
所以我们来颓柿子。
欢乐的颓柿子时间
令 ，。
那么上式 。
如果可以快速求出 ，那么就可以直接数论分块了。
那么 代表了什么呢？
不就是小于等于
的所有正整数中，和
互质的所有数的和嘛！
所以有 。
为什么是这样的呢？
当 时，显然没问题，。
当 时，如果 ，那么肯定也有 。
这告诉我们什么？不就是所有小于等于 的数种中与 互质的数的平均数为 嘛！
小于等于 的数中与 互质的数共有 个，所以上面式子没啥问题。
好，那么我们令 ，。
那么就有 。
既然
是一个积性函数，并且数据范围为 ，考虑使用杜教筛求解。
杜教筛
显然，，我们设
，下来搬出杜教筛的式子。
。
又怎么求呢？
。
这个直接求就可以了，
更简单，就不说了。
代码
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
| #include<unordered_map>
#include<cstdio>
using namespace std;
using ll=long long;
const int mod=1000000007;
const ll inv2=500000004;
const ll inv6=166666668;
inline int read()
{
int s=0,w=1;char ch;
while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
unordered_map<int,ll>mf;
int pri[1000001];
bool is[1000001];
ll f[1000001];
int n;
ll run(int l,int r)
{
return (ll)(r-l+1)*(l+r)/2%mod;
}
ll get(int n)
{
if(n<=1000000) return f[n];
if(mf.count(n)) return mf[n];
ll ans=(ll)n*(n+1)%mod*(2*n+1)%mod*inv6%mod;
for(int l=2,r;l<=n;l=r+1)
{
r=n/(n/l);
ans=(ans-run(l,r)*get(n/l))%mod;
}
return mf[n]=(ans+mod)%mod;
}
ll getS(int n)
{
ll ans=0;
for(int l=1,r;l<=n;l=r+1)
{
r=n/(n/l);
ans+=(r-l+1)*(get(n/l)+1)%mod*inv2%mod;
}
return ans%mod;
}
int main()
{
n=1000000,f[1]=1;
for(int i=2;i<=n;i++)
{
if(!is[i]) pri[++pri[0]]=i,f[i]=i-1;
for(int j=1;j<=pri[0]&&i*pri[j]<=n;j++)
{
is[i*pri[j]]=1;
if(i%pri[j]==0)
{
f[i*pri[j]]=f[i]*pri[j];
break;
}
f[i*pri[j]]=f[i]*(pri[j]-1);
}
}
for(int i=1;i<=n;i++) f[i]=(f[i]*i+f[i-1])%mod;
int l=read(),r=read();
printf("%lld\n",(getS(r)-getS(l-1)+mod)%mod);
return 0;
}
|