[文章目录]
Description
给定一个序列a[1],a[2],...,a[n]。求满足i!=j且a[i]|a[j]的二元组(i,j)的个数。n<=2000000,ai<=2000000
由于ai<=2000000，先将每个数的个数都统计出来。然后对于每个数暴力统计答案。如果之前统计过了，直接拿来用。复杂度
感觉这个复杂度很有用的样子。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,a[2001000],num[2001000],ans[2001000];
bool v[2001000];
long long fna;
int work(int x)
{
int re=0;
for(int i=x;i<=2000000;i+=x)
re+=num[i];
return re;
}
int read()
{
char ch=getchar();int re=0;
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9')
re=(re<<1)+(re<<3)+ch-'0',ch=getchar();
return re;
}
int main()
{
n=read();
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
num[a[i]]++;
}
for(int i=1;i<=n;i++)
{
if(!v[a[i]])
{
v[a[i]]=1;
ans[a[i]]=work(a[i]);
}
fna+=ans[a[i]];
}
printf("%lld\n",fna-n);
return 0;
}