隐藏
「51nod1239」欧拉函数之和 - 杜教筛 | Bill Yang's Blog

路终会有尽头,但视野总能看到更远的地方。

0%

「51nod1239」欧拉函数之和 - 杜教筛

题目大意

    求$\sum_{i=1}^n\varphi(i)\bmod1000000007$。


题目分析

杜教筛入门题。
下文为了方便,记$\phi(n)=\sum_{i=1}^n\varphi(i)$。

根据众所周知的结论:

有:

因此有:

此时我们得到了有关前缀和的递归式,递归计算即可。
根据积分,时间复杂度为$O(n^\frac34)$,若预处理$n^\frac23$内的$\phi(i)$,即可将时间复杂度将为$O(n^\frac23)$。

注意取模,特别是对$n$的取模!

本题还可以转化为莫比乌斯反演。
若我们不考虑对范围的限制,题目实际上让我们求$n$以内两两互质的数对个数,即:

如果我们能快速求出$\mu(i)$的前缀和即可得到答案,因此要用到莫比乌斯函数杜教筛

但是别忘了题目要求的是:

排除掉$(1,1)$除以$2$即可。

似乎这种方法要跑得快些。


代码

裸杜教筛。

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
70
71
72
73
74
75
76
77
78
79
80
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

typedef long long LL;
#define pii pair<LL,LL>
#define mp make_pair

inline const LL Get_Int() {
LL num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}

const int limit=5000000;
const LL mod=1000000007,inv=500000004,hashmod=999959;

bool vst[limit+5];
int cnt=0,Prime[limit+5];
LL Phi[limit+5];
vector<pii>Hash[hashmod+5];

void Table(int n) {
Phi[1]=1;
for(int i=2; i<=n; i++) {
if(!vst[i]) {
Prime[++cnt]=i;
Phi[i]=i-1;
}
for(int j=1; j<=cnt&&i*Prime[j]<=n; j++) {
vst[i*Prime[j]]=1;
if(i%Prime[j]==0) {
Phi[i*Prime[j]]=Phi[i]*Prime[j];
break;
}
Phi[i*Prime[j]]=Phi[i]*Phi[Prime[j]];
}
}
for(int i=2; i<=n; i++)Phi[i]=(Phi[i]+Phi[i-1])%mod;
}

void Add(int x,LL p,LL v) {
Hash[x].push_back(mp(p,v));
}

LL Cal(LL n) {
if(n<=limit)return Phi[n];
for(pii x:Hash[n%hashmod])if(x.first==n)return x.second;
LL next,ans=0;
for(LL i=2; i<=n; i=next+1) {
next=n/(n/i);
ans=(ans+(next-i+1)%mod*Cal(n/i)%mod)%mod;
}
ans=(n%mod*(n%mod+1)%mod*inv%mod-ans+mod)%mod;
Add(n%hashmod,n,ans);
return ans;
}

int main() {
Table(limit);
LL n=Get_Int();
printf("%lld\n",Cal(n));
return 0;
}

莫比乌斯反演+莫比乌斯函数杜教筛。

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

typedef long long LL;
#define pii pair<LL,LL>
#define mp make_pair

inline const LL Get_Int() {
LL num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}

const int limit=5000000;
const LL mod=1000000007,inv=500000004,hashmod=999959;

bool vst[limit+5];
int cnt=0,Prime[limit+5],Mobius[limit+5];
vector<pii>Hash[hashmod+5];

void Table(int n) {
Mobius[1]=1;
for(int i=2; i<=n; i++) {
if(!vst[i]) {
Prime[++cnt]=i;
Mobius[i]=-1;
}
for(int j=1; j<=cnt&&i*Prime[j]<=n; j++) {
vst[i*Prime[j]]=1;
if(i%Prime[j]==0) {
Mobius[i*Prime[j]]=0;
break;
}
Mobius[i*Prime[j]]=-Mobius[i];
}
}
for(int i=2; i<=n; i++)Mobius[i]+=Mobius[i-1];
}

void Add(int x,LL p,LL v) {
Hash[x].push_back(mp(p,v));
}

LL Cal(LL n) {
if(n<=limit)return Mobius[n];
for(pii x:Hash[n%hashmod])if(x.first==n)return x.second;
LL Next,ans=0;
for(LL i=2; i<=n; i=Next+1) {
Next=n/(n/i);
ans+=(Next-i+1)*Cal(n/i);
}
ans=1-ans;
Add(n%hashmod,n,ans);
return ans;
}

int main() {
Table(limit);
LL n=Get_Int(),next,ans=0;
for(LL i=1; i<=n; i=next+1) {
next=n/(n/i);
ans=(ans+((n/i)%mod*((n/i)%mod)%mod*(Cal(next)-Cal(i-1))%mod+mod)%mod)%mod;
}
printf("%lld\n",((ans-1)%mod*inv%mod+1)%mod);
return 0;
}

姥爷们赏瓶冰阔落吧~