隐藏
「2014NOI模拟8」老逗的gcd - 莫比乌斯反演+线性筛 | Bill Yang's Blog

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

0%

「2014NOI模拟8」老逗的gcd - 莫比乌斯反演+线性筛

题目大意

    对于给定的$n,m$,求$\sum_{i=1}^n\sum_{j=1}^mf(i,j)$。
    其中,函数$f(x,y)$的定义为:


题目分析

墙角膜liuguangzhe大佬。

根据莫比乌斯函数的性质有:

令$f(x)=\sum_{i\mid x}\mu^2(i)\mu(\frac xi)i$,则原式为:

若$f$函数可以很快求出,则原式可以用分块加速在$O(\sqrt n)$的时间内求出。
考虑$f$函数,若$p$是一个质数,则:

而$f$函数是积性函数卷积、乘积起来,故也是一个积性函数,因此可以线性筛。


代码

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
#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

inline int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(!isdigit(x)) {if(x=='-')bj=-1;x=getchar();}
while(isdigit(x)) {num=num*10+x-'0';x=getchar();}
return num*bj;
}

const int maxn=10000005;

int n,m,cnt=0,p[maxn];
bool vst[maxn];
LL f[maxn];

void Sieve(int n) {
f[1]=1;
for(int i=2; i<=n; i++) {
if(!vst[i]) {p[++cnt]=i;f[i]=i-1;}
for(int j=1; j<=cnt&&i*p[j]<=n; j++) {
vst[i*p[j]]=1;
if(i%p[j]==0) {
f[i*p[j]]=i%(p[j]*p[j])==0?0:-f[i]/(p[j]-1)*p[j];
break;
}
f[i*p[j]]=f[i]*f[p[j]];
}
}
for(int i=2; i<=n; i++)f[i]+=f[i-1];
}

int main() {
Sieve(10000000);
int t=Get_Int();
while(t--) {
n=Get_Int();
m=Get_Int();
LL ans=0;
for(int i=1,next=0; i<=min(n,m); i=next+1) {
next=min(n/(n/i),m/(m/i));
ans+=(f[next]-f[i-1])*(n/i)*(m/i);
}
printf("%lld\n",ans);
}
return 0;
}
姥爷们赏瓶冰阔落吧~