CF1780F Three Chairs
题目描述
One day Kira found
n
n
n friends from Morioh and decided to gather them around a table to have a peaceful conversation. The height of friend
i
i
i is equal to
a
i
a_i
ai . It so happened that the height of each of the friends is unique.
Unfortunately, there were only
3
3
3 chairs in Kira’s house, and obviously, it will not be possible to seat all friends! So, Kira has to invite only
3
3
3 of his friends.
But everything is not so simple! If the heights of the lowest and the tallest of the invited friends are not coprime, then the friends will play tricks on each other, which will greatly anger Kira.
Kira became interested, how many ways are there to choose
3
3
3 of his friends so that they don’t play tricks? Two ways are considered different if there is a friend invited in one way, but not in the other.
Formally, if Kira invites friends
i
i
i ,
j
j
j , and
k
k
k , then the following should be true:
gcd
(
min
(
a
i
,
a
j
,
a
k
)
,
max
(
a
i
,
a
j
,
a
k
)
)
=
1
gcd(min(a_i, a_j, a_k), max(a_i, a_j, a_k)) = 1
gcd(min(ai,aj,ak),max(ai,aj,ak))=1 , where
gcd
(
x
,
y
)
gcd(x, y)
gcd(x,y) denotes the greatest common divisor (GCD) of the numbers
x
x
x and
y
y
y .
Kira is not very strong in computer science, so he asks you to count the number of ways to invide friends.
题意简述
给一个长度为
n
n
n 的数组
a
a
a，数字两两不同。求有多少个三元组
(
a
i
,
a
j
,
a
k
)
(a_i,a_j,a_k)
(ai,aj,ak)，满足
i
<
j
<
k
i<j<k
i<j<k 且
gcd
(
a
i
,
a
k
)
=
1
gcd(a_i,a_k)=1
gcd(ai,ak)=1。
题解
首先给
a
a
a 数组从小到大排序，容易想到枚举
i
,
k
i,k
i,k，若
gcd
(
a
i
,
a
k
)
=
1
gcd(a_i,a_k)=1
gcd(ai,ak)=1，则对答案有
(
k
−
i
−
1
)
(k-i-1)
(k−i−1) 的贡献。
由此可得
a
n
s
=
∑
k
=
1
n
∑
i
=
1
k
−
1
[
gcd
(
a
i
,
a
k
)
=
1
]
(
k
−
i
−
1
)
ans=sumlimits_{k=1}^nsumlimits_{i=1}^{k-1}left[gcd(a_i,a_k)=1right](k-i-1)
ans=k=1∑ni=1∑k−1[gcd(ai,ak)=1](k−i−1)
根据莫比乌斯函数的性质
∑
d
∣
n
μ
(
d
)
=
[
n
=
1
]
sumlimits_{dmid n}mu(d)=[n=1]
d∣n∑μ(d)=[n=1]，有
∑
k
=
1
n
∑
i
=
1
k
−
1
∑
d
∣
gcd
(
a
i
,
a
k
)
μ
(
d
)
(
k
−
i
−
1
)
sumlimits_{k=1}^nsumlimits_{i=1}^{k-1}sumlimits_{dmidgcd(a_i,a_k)}mu(d)(k-i-1)
k=1∑ni=1∑k−1d∣gcd(ai,ak)∑μ(d)(k−i−1)
因为
d
∣
gcd
(
a
i
,
a
k
)
dmidgcd(a_i,a_k)
d∣gcd(ai,ak)，所以
d
∣
a
i
∧
d
∣
a
k
dmid a_iland dmid a_k
d∣ai∧d∣ak，二者是等价的。
先枚举
d
d
d，有
∑
d
=
1
a
n
μ
(
d
)
∑
d
∣
a
k
∑
d
∣
a
i
∧
i
<
k
(
k
−
i
−
1
)
sumlimits_{d=1}^{a_n}mu(d)sumlimits_{dmid a_k}sumlimits_{dmid a_iland i<k}(k-i-1)
d=1∑anμ(d)d∣ak∑d∣ai∧i<k∑(k−i−1)
为了方便，继续化简式子
∑
d
=
1
a
n
μ
(
d
)
∑
d
∣
a
k
(
n
u
m
⋅
(
k
−
1
)
−
∑
d
∣
a
i
∧
i
<
k
i
)
sumlimits_{d=1}^{a_n}mu(d)sumlimits_{dmid a_k}left(numcdot(k-1)-sumlimits_{dmid a_iland i<k}iright)
d=1∑anμ(d)d∣ak∑
num⋅(k−1)−d∣ai∧i<k∑i
n
u
m
num
num 表示满足
d
∣
a
i
∧
i
<
k
dmid a_iland i<k
d∣ai∧i<k 的数量。
观察这个式子，
μ
mu
μ 可以
O
(
a
n
)
O(a_n)
O(an) 预处理，对于后半部分的式子，我们可以枚举
d
d
d 的倍数
x
x
x，若
x
x
x 是某个
a
k
a_k
ak 就可以进行计算。
因为
d
∣
a
k
,
d
∣
a
i
dmid a_k,dmid a_i
d∣ak,d∣ai ，又
i
<
k
i<k
i<k ，所以
a
i
a_i
ai 一定是之前访问过的。
这样，
n
u
m
num
num 可以快速求得，用
s
u
m
sum
sum 记录前面满足
d
∣
a
i
∧
i
<
k
dmid a_iland i<k
d∣ai∧i<k 的
i
i
i 的和，遇到
d
∣
a
k
dmid a_k
d∣ak 时先算现在的贡献，再
n
u
m
←
n
u
m
+
1
,
s
u
m
←
s
u
m
+
k
numgets num+1,sumgets sum+k
num←num+1,sum←sum+k。
总的时间复杂度为
O
(
n
log
n
+
a
n
ln
a
n
)
O(nlog n+a_nln a_n)
O(nlogn+anlnan)
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3e5+1;
int pd[N],mu[N],p[N],cnt,a[N],n,t[N];
ll ans;
int main()
{
pd[1]=mu[1]=1;
for(int i=2;i<N;i++){
if(!pd[i]) p[++cnt]=i,mu[i]=-1;
for(int j=1;j<=cnt&&i*p[j]<N;j++){
pd[i*p[j]]=1;
if(i%p[j]==0) break;
mu[i*p[j]]=-mu[i];
}
}
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
sort(a+1,a+1+n);
for(int i=1;i<=n;i++) t[a[i]]=i;//记录每个a_i的下标
for(int d=1;d<=a[n];d++){
ll Sum=0,num=0,sum=0;
for(int x=d;x<=a[n];x+=d){//枚举d的倍数x
if(t[x]){//t_x就是当前的k
Sum+=num*(t[x]-1)-sum;//加上当前的贡献
num++,sum+=t[x];//处理num,sum,为下次作准备
}
}
ans+=mu[d]*Sum;
}
cout<<ans;
}