自动搬运

查看原文

来自洛谷，原作者为

	KSCD_ 知不可乎骤得，知来者之可追. | Defection,Retribution,Testify. | Rotating_Catfood

搬运于2025-08-24 22:57:30，当前版本为作者最后更新于2024-06-20 10:51:33，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路

（是 @Iceturky 的思路，在此拜谢）

值域小，为了方便表示设值域 $P={10}^5$。先开桶 $t_x$ 表示 $x$ 出现的次数。同时预处理出每个数编号不相等的因数个数 $s_x$ 和倍数个数 $b_x$，时间复杂度为调和级数 $O(P\ln P)$。

考虑先算出 $i\ne j$ 且 $a_i\mid a_j$ 的 $(i,j)$ 数量 $m$，枚举较小数 $x$，得 $m=\sum_{x=1}^{P}t_x\times b_x$。

有了以上问题的答案，平方一下就是 $a_i\mid a_k,a_j\mid a_l$ 且 $i\ne k,j\ne l$ 的 $(i,j,k,l)$ 组数，还需要容斥减去 $i=j,i=l,k=j,k=l$ 的组数。

首先先减去满足一个条件的：

• $i=j$，较小数相等，枚举这个数 $x$，取两个倍数，组数为 $\sum_{x=1}^P t_x\times b_x^2$。
• $k=l$，较大数相等，枚举这个数 $x$，取两个因数，组数为 $\sum_{x=1}^P t_x\times s_x^2$。
• $i=l$ 或 $j=k$，即一组中较大数与另一组中较小数相等。枚举相等的中间值 $x$，取一个因数和一个倍数，组数为 $\sum_{x=1}^P 2(t_x\times b_x\times s_x)$。

还需要加上满足两个条件的：

• $i=j$ 且 $k=l$，此时两个较小数和两个较大数分别相等，组数即为最初求出的 $(i,j)$ 数量 $m$。
• $i=l$ 且 $j=k$，由于倍数的要求限制了 $i\le k,j\le l$，所以此时 $i,j,k,l$ 均相等，枚举相等值 $x$，组数为 $\sum_{x=1}^Pt_x(t_x-1)$。
• 其他四种情况都会产生 $i=k$ 或 $j=l$，与已经确定的条件 $i\ne k,j\ne l$ 冲突，所以组数为 $0$。

之后满足三个或四个条件也会产生同样的冲突，组数均为 $0$，不用处理。

这样就做完了，但是由于 $n^4$ 达到了 ${10}^{20}$ 级别，开 __int128 才能确保通过。

代码

#include<iostream>
#define int __int128
using namespace std;
const int N=1e5+10;
const int P=1e5;
int read()
{
	int s=0,w=1;
	char ch; ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-') w=-1; ch=getchar();}
	while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
	return s*w;
}
void print(int x)
{
	if(x>=10) print(x/10);
	putchar(x%10+'0');
}
int n,ans,t[N],s[N],b[N];
signed main()
{
	n=read();
	for(int i=1;i<=n;i++) t[read()]++;
	for(int i=1;i<=P;i++) if(t[i])
	{
		for(int j=i*2;j<=P;j+=i) if(t[j])
			b[i]+=t[j],s[j]+=t[i];
		b[i]+=t[i]-1,s[i]+=t[i]-1;
		ans+=t[i]*b[i];
	}
	ans*=(ans+1); //无限制和 i=k && j=l 
	for(int i=1;i<=P;i++) if(t[i])
	{
		ans-=t[i]*b[i]*b[i]; // i=j
		ans-=t[i]*s[i]*s[i]; // k=l
		ans-=2*t[i]*b[i]*s[i]; // i=l || j=k
		ans+=t[i]*(t[i]-1); // i=l && j=k 
	}
	print(ans);
	return 0;
}