题意
题意：已知 ，求 ，其中 。
题目链接
题解
首先我们先来看一个结论：。其中
表示在 成立的时候这个值为 ，不成立时这个值为 。
为啥这个结论是对的呢？前面的
实际上是在枚举这个约数的值，但是为什么在 后面还要乘上一个数字呢？
因为如果不乘那个数字会重复计算，例如在 时 和 这两组取值都可以得到一个 的约数 ，这时候这个约数就被计算了两遍。加上这个约束就不会重复计算了。
下来我们来推式子。
欢乐的颓柿子时间
令
那么上面的式子可以变成 。
可以发现，如果可以比较快速求出 的值以及
的前缀和就可以对整个式子进行数论分块。
Part1
我们先来看一下 的值如何求。
这个玩意也可以数论分块（瞬间窒息
Part2
我们设 。
那么我们要求的 。
既然要在
范围内求一个函数（就是 ）的前缀和，并且这还是一个积性函数，我们首先考虑杜教筛。
不难发现 ，那我们设
。
让我们把杜教筛的式子写出来：
的前缀和挺好求，不说了。
我们来推一下 的。 Game over!
数论分块套数论分块，时间复杂度为 。
代码
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
| #include<cstdio>
#include<map>
using namespace std;
const int mod=1000000007;
using ll=long long;
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;
}
int pri[1000001];
bool is[1000001];
ll f[1000001];
map<int,ll>mf;
ll ans;
int n;
ll run(int l,int r)
{
return (ll)(r-l+1)*(l+r)/2%mod;
}
ll get(int num)
{
if(num<=1000000) return f[num];
if(mf.count(num)) return mf[num];
ll val=1;
for(int l=2,r;l<=num;l=r+1)
{
r=num/(num/l);
val=(val-run(l,r)*get(num/l))%mod;
}
return mf[num]=(val+mod)%mod;
}
ll getpre(int num)
{
ll ans=0;
for(int l=1,r;l<=num;l=r+1)
{
r=num/(num/l);
ans=(ans+run(l,r)*(num/l))%mod;
}
return ans*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]=-1;
for(int j=1;j<=pri[0]&&i*pri[j]<=n;j++)
{
is[i*pri[j]]=1;
if(i%pri[j]==0) break;
f[i*pri[j]]=-f[i];
}
}
for(int i=1;i<=n;i++) f[i]=(f[i]*i+f[i-1]+mod)%mod;
n=read();
for(int l=1,r;l<=n;l=r+1)
{
r=n/(n/l);
ans=(ans+(get(r)-get(l-1))*getpre(n/l))%mod;
}
printf("%lld\n",(ans+mod)%mod);
return 0;
}
|