[省选联考 2021 B 卷] 数对 题解

题目描述

给定 \(n\) 个正整数 \(a_i\)，请你求出有多少个数对 \((i, j)\) 满足 \(1 \le i \le n\)，\(1 \le j \le n\)，\(i \ne j\) 且 \(a_i\) 是 \(a_j\) 的倍数。

提示

对于 \(40 \%\) 的数据，\(n \le 1000\)。
对于 \(70 \%\) 的数据，\(1 \le a_i \le 5 \times {10}^3\)。
对于 \(100 \%\) 的数据，\(2 \le n \le 2 \times {10}^5\)，\(1 \le a_i \le 5 \times {10}^5\)。

题解

开个桶，对每个数枚举倍数，做完了。

代码：

#include<bits/stdc++.h>
#define For(i,l,r) for(int i=(l);i<=(r);++i)
typedef long long ll;
const int N=500010;
using namespace std;
int n;
int cnt[N];
ll ans;
int main()
{
	scanf("%d",&n);
	For(i,1,n)
	{
		int x;
		scanf("%d",&x);
		++cnt[x];
	}
	For(i,1,N-10)
	{
		if(cnt[i]!=0)
		{
			ans+=(1ll*cnt[i]*(cnt[i]-1));
			for(int j=2;j*i<=(N-10);++j)
				ans+=(1ll*cnt[i]*cnt[j*i]);
		}
	}
	printf("%lld",ans);
	return 0;
}