P2714 四元组统计题解

JJL0610 / 2023-07-17 / 原文

前言

为了纪念 长沙市一中 第一次思维训练，我写下这篇题解。

传送门

题目描述

有 $n$ 个正整数 $a_i$，你要统计有多少个四元组满足 $\gcd(a_i,a_j,a_k,a_l) = 1$。

思路分析

我们使用容斥遍历每一个 $\gcd(a_i,a_j,a_k,a_l) = x$ 的个数，储存在 $f_x$ 中，一直到 $1$ 的答案出现。

实现

得到 $x=2$ 时的个数，我们使用组合，也就是从序列中随便选取 $4$ 个包含 $2$ 的数，这时我们的方案数就是 $C_{m_{2}}^{4}$。

仅仅是这样吗？

No!

如果这四个数都包含 $4$ 呢？我们就重复算了 $x=4$ 的个数，这时候不仅是 $4$ 所有 $2$ 的倍数全部都被算了一遍。

所以我们可以把多算的全部减去：

$$f_i=C_{m_i}^4-{\sum _{j=i\times2}^{maxn}[j|i] f_j} $$

那么就得出了答案。

注：$\sum _{j=i\times2}^{maxn}[j|i] f_j$ 意思为查找 $i$ 的倍数 $j$ 的方案数的累加。

AC Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,maxn=-1;
int g[10010],f[10010];
void check(int x){
	for(int i=1;i<=sqrt(x);++i){
		if(x%i==0){
			g[i]++;
			if(i*i!=x){
				g[x/i]++;		
			}	
		}	
	}
}//查找每一个因数

int C(int n,int m)
{
	int ans=1;
	for (int i=1;i<=n;i++){
		ans=ans*(m-i+1);
		ans=ans/i;
	}
	return ans;
}//组合公式

signed main(){
	while(cin>>n){
		memset(g,0,sizeof(g));
		memset(f,0,sizeof(f));
		for(int i=1,s;i<=n;i++){
			cin>>s;
			check(s);
			maxn=max(maxn,s);	
		}
		for(int i=maxn;i>=1;i--){
			f[i]=C(4,g[i]);
			for(int j=i*2;j<=maxn;j+=i){
				f[i]-=f[j];//容斥，去除算了两次的。
			}
		}
		cout<<f[1]<<endl;//输出答案。
	}
	
}
/*
4
2 3 4 5
4
2 4 6 8
7
2 3 4 5 7 6 8
*/