隐藏
「bzoj2694」LCM - 莫比乌斯反演+线性筛 | Bill Yang's Blog

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

0%

「bzoj2694」LCM - 莫比乌斯反演+线性筛

题目大意

    定义整数$A,B$,求所有满足如下条件的$lcm(a,b)$的和:

    输出答案模$2^{30}$。


题目分析

类似这道题

令$g(x)=\frac {x(x+1)}2$,则:

令$f(x)=\sum_{i\mid x}\mu^2(i)\mu(\frac xi)\frac{x^2}i$。
不难发现

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

using namespace std;

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],g[maxn];
bool vst[maxn];

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

int f(int x) {return x*(x+1)/2;}

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