隐藏
「bzoj2226」「Spoj5971」LCMSum - 莫比乌斯反演 | Bill Yang's Blog

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

0%

「bzoj2226」「Spoj5971」LCMSum - 莫比乌斯反演

题目大意

    计算$\sum_{i=1}^nlcm(i,n)$。


题目分析

令$f[d]=\sum\limits_{i=1}^{d}i[\gcd(i,d)=1]$,故原式为:$n\sum\limits_{d\mid n}f[d]$。
考虑如何求$f[d]$,我们发现$f[d]$有具体意义:比$d$小且与$d$互质的数之和,在本处我们讲过$f[d]=\frac{d\varphi(d)}2$。
故答案为:

一种解法是线性筛$\varphi$,对于询问$O(\sqrt n)$回答,总时间复杂度$O(T\sqrt n)$,无法通过(似乎有人卡常数过了)。
我们可以用$O(n\log n)$的时间进行预处理将答案普通筛一遍,回答询问就是$O(1)$的了。

另:本题似乎有其他反演的方式,最后可以直接线性筛得出答案。


代码

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
#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;

inline const int Get_Int() {
int 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 maxn=1000005;

LL n,ans[maxn];
int cnt=0,Prime[maxn],Phi[maxn];
bool vst[maxn];

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]];
}
}
}

int main() {
Table(1000000);
for(int i=2; i<=1000000; i++)
for(int j=i; j<=1000000; j+=i)
ans[j]+=(LL)i*Phi[i]/2;
int t=Get_Int();
while(t--) {
n=Get_Int();
printf("%lld\n",(ans[n]+1)*n);
}
return 0;
}
姥爷们赏瓶冰阔落吧~