线性容斥
题意
题目大意：有一个长度为n的数组a，如果对于一个数个(a[i],a[j]）满足不存在a[k]使a[i]%a[k]=0且a[j]%a[k]=0，则称这个数对是合法的，求合法数对的数量。
思路
对于任意一个a[k],如果这个数合法,则**没有点对（i，j)**，满足$gcd(a[i],a[j])%a[k]=0$
考虑单点贡献，因为点对贡献是$O(n^2)$的复杂度
考虑dp，设$dp[g]$表示$gcd(a[i],a[j])=g$的点对数，则$ans=\sum_{a_k\nmid g\forall k\in[1,n]}dp_g$
具体如何求$dp[g]$：如果我们知道一个多重集合中，任意两个数的gcd都是g的倍数，那么就好做了
dp[g]=C(cnt,2)-dp[2*g]-dp[3*g]-…dp[k*g](C表示组合数，cnt表示集合中的多重集中元素个数)
代码
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;
const int N=1e6+5;
ll dp[N];
ll a[N];
ll cnt[N];
ll n;
bool biaoji[N];
void solve()
{
cin>>n;
for(int i=1;i<=n;i++){
dp[i]=cnt[i]=biaoji[i]=0;
}
for(int i=1;i<=n;i++){
cin>>a[i];
cnt[a[i]]++;
}
ll zong=0;
for(ll g=n;g>=1;g--){
ll sum=cnt[g];
for(ll k=2;k*g<=n;k++){
dp[g]-=dp[k*g];
sum+=cnt[k*g];
}
dp[g]+=sum*(sum-1)/2;
}
for(ll i=1;i<=n;i++){
if(!cnt[i])continue;
for(ll j=1;j*i<=n;j++){
biaoji[j*i]=1;
}
}
ll ans=0;
for(int i=1;i<=n;i++){
if(!biaoji[i]){
ans+=dp[i];
}
}
cout<<ans<<endl;
}
int main()
{
int t=0;
cin>>t;
while(t--){
solve();
}
return 0;
}
|
注意，最后要算点对数，而不是a[k]的数目，所以关键是判断哪些点对合法。
而dp[g]就是表示gcd恰好等于g的所有点对数，所以只需要判断哪些g合法即可