解题思路
其实你只要知道:
这题你就秒了。
我们发现 ,于是开一个桶来统计每个数出现的数量。
我们只需要枚举每一个数的倍数,然后统计。
最后,如果一个数出现了多次,再特判一下即可。
代码
#include<bits/stdc++.h>
using namespace std;
int n;
int cnt[500001];
int mx;
long long ans;
long long temp;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n;
int x;
for(int i=1;i<=n;i++)
{
cin>>x;
mx=max(mx,x);
cnt[x]++;
}
for(int i=1;i<=mx;i++)
{
temp=0;
for(int j=2;j<=mx/i;j++)
{
temp+=cnt[i*j];
}
temp+=cnt[i]-1;
temp*=cnt[i];
ans+=temp;
}
cout<<ans;
return 0;
}
标签:P7517,cnt,int,数对,cin,long,mx,tie,联考
From: https://blog.csdn.net/2403_87021226/article/details/142723224