正题
题目链接:https://www.luogu.com.cn/problem/P3911
题目大意
给出数列 A A A求 ∑ i = 1 n ∑ j = 1 n l c m ( A i , A j ) \sum_{i=1}^n\sum_{j=1}^nlcm(A_i,A_j) i=1∑nj=1∑nlcm(Ai,Aj)
解题思路
设
c
i
c_i
ci表示
A
j
=
i
A_j=i
Aj=i的个数，然后答案就是（下面
n
=
5
e
4
n=5e4
n=5e4）
∑
i
=
1
n
∑
j
=
1
n
l
c
m
(
i
,
j
)
c
i
c
j
\sum_{i=1}^n\sum_{j=1}^nlcm(i,j)c_ic_j
i=1∑nj=1∑nlcm(i,j)cicj
∑
i
=
1
n
∑
j
=
1
n
i
j
g
c
d
(
i
,
j
)
c
i
c
j
\sum_{i=1}^n\sum_{j=1}^n\frac{ij}{gcd(i,j)}c_ic_j
i=1∑nj=1∑ngcd(i,j)ijcicj
∑
x
=
1
n
x
∑
i
=
1
⌊
n
x
⌋
∑
j
=
1
⌊
n
x
⌋
[
g
c
d
(
i
,
j
)
=
=
1
]
i
j
c
i
∗
x
c
j
∗
x
\sum_{x=1}^nx\sum_{i=1}^{\lfloor\frac{n}{x}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{x}\rfloor}[gcd(i,j)==1]ijc_{i*x}c_{j*x}
x=1∑nxi=1∑⌊xn⌋j=1∑⌊xn⌋[gcd(i,j)==1]ijci∗xcj∗x
然后反演一下
∑
x
=
1
n
∑
x
∣
d
μ
(
d
x
)
d
∑
i
=
1
⌊
n
d
⌋
∑
j
=
1
⌊
n
d
⌋
i
j
c
i
∗
d
c
j
∗
d
\sum_{x=1}^n\sum_{x|d}\mu(\frac{d}{x})d\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}ijc_{i*d}c_{j*d}
x=1∑nx∣d∑μ(xd)di=1∑⌊dn⌋j=1∑⌊dn⌋ijci∗dcj∗d
∑
d
=
1
n
d
∑
x
∣
d
μ
(
d
x
)
∑
i
=
1
⌊
n
d
⌋
∑
j
=
1
⌊
n
d
⌋
i
j
c
i
∗
d
c
j
∗
d
\sum_{d=1}^nd\sum_{x|d}\mu(\frac{d}{x})\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}ijc_{i*d}c_{j*d}
d=1∑ndx∣d∑μ(xd)i=1∑⌊dn⌋j=1∑⌊dn⌋ijci∗dcj∗d
然后两部分分开处理就好了，时间复杂度
O
(
n
log
n
)
O(n\log n)
O(nlogn)
c o d e code code
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const ll N=5e4+10;
ll n,cnt,pri[N],mu[N],c[N],g[N],f[N],ans;
bool v[N];
void prime(){
mu[1]=1;
for(ll i=2;i<N;i++){
if(!v[i])pri[++cnt]=i,mu[i]=-1;
for(ll j=1;j<=cnt&&i*pri[j]<N;j++){
v[i*pri[j]]=1;
if(i%pri[j]==0)break;
mu[i*pri[j]]=mu[i]*mu[pri[j]];
}
}
for(ll i=1;i<N;i++)
for(ll j=i;j<N;j+=i)
g[j]+=mu[i]*i;
return;
}
int main()
{
prime();
scanf("%lld",&n);
for(ll i=1;i<=n;i++){
ll x;
scanf("%lld",&x);
c[x]++;
}
for(ll i=1;i<N;i++)
for(ll j=1;i*j<N;j++)
f[i]+=c[i*j]*j;
for(ll i=1;i<N;i++)
ans+=f[i]*f[i]*i*g[i];
printf("%lld\n",ans);
return 0;
}