题目链接:

http://acm.hdu.edu.cn/showproblem.php?pid=5072
题意:给n个数,从中选三个,三个数满足条件的要求是:三个数中两两互质或两两不互质,问满足条件的个数?

转换成求满足条件的反面:
①:a和b,c互质,b和c不互质
②:a和b,c不互质,b和c互质
于是就是枚举每个数,找出与他互质的个数与不互质的个数
答案就是:互质个数*不互质个数/2
至于为什么要除2,我看得还不是很懂

然后就变成了:怎样快速统计cnt个数与x互质的个数?
以前看过m以内与x互质的个数,也是容斥来求,但是那是m以内的每个数,而现在是随便cnt个数,这cnt个数长什么样子都不知道,怎么办呢?

我们看这个数与其他数互不互质就是看这个数与其他数有没有公共的质因子,如果有,那就不互质,于是就筛出这n个数中含有某个因子 i 的个数,用cnt2[i] 来表示
那么看某个数着n个数中的某个数 x 与他<mark>不互质</mark>的个数就是:
<mark>有一个公共质因子的个数 - 有两个公共质因子的个数+有三个公共质因子的个数…</mark>

其实感觉跟质因子有关的容斥,就跟莫比乌斯函数有关,上面的容斥系数就是莫比乌斯函数,所以阔以用莫比乌斯函数来直接求与这个数 x <mark>互质</mark>的个数

①容斥做

#include"bits/stdc++.h"
using namespace std;
typedef long long LL;
const int maxn=1e5+5;
const int MOD=1e9+7;
int cnt1[maxn];//记录i这个数有多少个
int cnt2[maxn];//看含有因子i 的数有多少个
vector<LL>factor[maxn];//用来保存这个数的质因子
vector<LL>prime;
int mu[maxn];
LL Max;
LL N;
bool vis[maxn];
void PHI(int n)
{
	memset(vis,1,sizeof(vis));
	mu[1]=1;
	for(int i=2; i<=n; i++)
	{
		if(vis[i])
		{
			prime.push_back(i);
			mu[i]=-1;
		}
		for(int j=0; j<prime.size()&&i*prime[j]<=n; j++)
		{
			vis[i*prime[j]]=0;
			if(i%prime[j]==0)
			{
				mu[i*prime[j]]=0;
				break;
			}
			else mu[i*prime[j]]=-mu[i];
		}
	}
}
void fenjie(LL n)//分解质因子
{
	if(factor[n].size())return ;
	LL t=0,m=n;
	while(n>1)
	{
		if(n%prime[t]==0)
		{
			factor[m].push_back(prime[t]);
			while(n%prime[t]==0)n/=prime[t];
		}
		if(prime[t]*prime[t]>n)break;
		t++;
	}
	if(n>1)factor[m].push_back(n);
}
LL calc(LL n)//计算这个数与其他数互质的个数
{
	LL res=0;
	LL cnt=factor[n].size();
	for(int sta=1; sta<(1<<cnt); sta++)
	{
		LL tp=1;
		for(int j=0; j<cnt; j++)
		{
			if(sta&(1<<j))tp*=factor[n][j];
		}
		if(__builtin_popcount(sta)%2)res+=cnt2[tp]-1;//减1是减去他自己
		else res-=cnt2[tp]-1;
	}
	return res;
}
int a[maxn];
int main()
{
	PHI(maxn-5);
	int T;
	cin>>T;
	while(T--)
	{
		LL Max=0;
		for(int i=0;i<=100000;i++)cnt1[i]=cnt2[i]=0;
		cin>>N;
		for(int i=1; i<=N; i++)
		{
			int t;
			scanf("%d",a+i);
			Max=max(Max,(LL)a[i]);
			cnt1[a[i]]++;
			fenjie(a[i]);
		}
		for(int t=1; t<=Max; t++)for(int k=1; k*t<=Max; k++)cnt2[t]+=cnt1[k*t]; //枚举t的倍数 
		LL res=0;
		for(int i=1;i<=N;i++)
		{
			LL tp;
			tp=calc(a[i]);//求的是与他不互质的个数 
			res+=(N-1-tp)*tp;
		}
		cout<<N*(N-1)*(N-2)/6-res/2<<endl;
	}
}

②莫比乌斯函数来求

直接求会T,但是好理解

求答案的时间大概要400+ms,然后前面还有100+ms,一共5组数据,就会T

#include"bits/stdc++.h"
using namespace std;
typedef long long LL;
const int maxn=1e5+5;
const int MOD=1e9+7;
int cnt1[maxn];//记录i这个数有多少个
int cnt2[maxn];//看含有因子i 的数有多少个
vector<LL>factor[maxn];//用来保存这个数的质因子
vector<LL>prime;
int mu[maxn];
LL Max;
LL N;
bool vis[maxn];
void PHI(int n)
{
	memset(vis,1,sizeof(vis));
	mu[1]=1;
	for(int i=2; i<=n; i++)
	{
		if(vis[i])
		{
			prime.push_back(i);
			mu[i]=-1;
		}
		for(int j=0; j<prime.size()&&i*prime[j]<=n; j++)
		{
			vis[i*prime[j]]=0;
			if(i%prime[j]==0)
			{
				mu[i*prime[j]]=0;
				break;
			}
			else mu[i*prime[j]]=-mu[i];
		}
	}
}
LL calc(LL n)//直接用莫比乌斯函数来容斥 ,求的是与n互质的个数
{
	if(n==1)return 0;
	LL res=0;
	for(LL i=1; i*i<=n; i++)
	{
		if(n%i)continue;
		res+=mu[i]*cnt2[i];
		if(i==n/i)continue;
		res+=mu[n/i]*cnt2[n/i];
	}
	return res;
}
int a[maxn];
int main()
{
	PHI(maxn-5);
	int T;
	cin>>T;
	while(T--)
	{
		LL Max=0;
		for(int i=0;i<=100000;i++)cnt1[i]=cnt2[i]=0;
		cin>>N;
		for(int i=1; i<=N; i++)
		{
			int t;
			scanf("%d",a+i);
			Max=max(Max,(LL)a[i]);
			cnt1[a[i]]++;
		}
		for(int t=1; t<=Max; t++)for(int k=1; k*t<=Max; k++)cnt2[t]+=cnt1[k*t]; //枚举t的倍数
		LL res=0;
		for(int i=1;i<=N;i++)
		{
			LL tp;
			tp=calc(a[i]);//求的是与他互质的个数,会超时 
			res+=(N-1-tp)*tp;
		}
		cout<<N*(N-1)*(N-2)/6-res/2<<endl;
	}
}

计算每个因子的贡献

就是说上面每个数求的时候,阔以把每个因子的贡献一口气加到他所有的倍数上,这样就能节约很多时间。这种方法就是很常见的优化方法,也是我学这种的时候智商不够用的方法

#include"bits/stdc++.h"
using namespace std;
typedef long long LL;
const int maxn=1e5+5;
const int MOD=1e9+7;
int cnt1[maxn];//记录i这个数有多少个
int cnt2[maxn];//看含有因子i 的数有多少个
int cnt3[maxn];//用来保存n个数中与i这个数互质的有几个
vector<LL>factor[maxn];//用来保存这个数的质因子
vector<LL>prime;
int mu[maxn];
LL Max;
LL N;
bool vis[maxn];
void PHI(int n)
{
	memset(vis,1,sizeof(vis));
	mu[1]=1;
	for(int i=2; i<=n; i++)
	{
		if(vis[i])
		{
			prime.push_back(i);
			mu[i]=-1;
		}
		for(int j=0; j<prime.size()&&i*prime[j]<=n; j++)
		{
			vis[i*prime[j]]=0;
			if(i%prime[j]==0)
			{
				mu[i*prime[j]]=0;
				break;
			}
			else mu[i*prime[j]]=-mu[i];
		}
	}
}
int a[maxn];
int main()
{
	PHI(maxn-5);
	int T;
	cin>>T;
	while(T--)
	{
		int Max=0;
		for(int i=0; i<=100000; i++)cnt1[i]=cnt2[i]=cnt3[i]=0;
		cin>>N;
		for(int i=1; i<=N; i++)
		{
			scanf("%d",a+i);
			Max=max(Max,a[i]);
			cnt1[a[i]]++;
		}
		for(int t=1; t<=Max; t++)
		{
			//枚举t的倍数,计算t这个数对倍数的贡献
			for(int k=1; k*t<=Max; k++)cnt2[t]+=cnt1[k*t];//计算是t的倍数的数有几个
			for(int k=1; k*t<=Max; k++)cnt3[t*k]+=mu[t]*cnt2[t]; //计算t的贡献
		}
		LL res=0;
		for(int i=1; i<=N; i++)
		{
			if(a[i]==1||cnt3[a[i]]==0)continue;
			res+=cnt3[a[i]]*(N-1-cnt3[a[i]]);
		}
		cout<<N*(N-1)*(N-2)/6-res/2<<endl;
	}
}