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

### Preface 套路题，很显然很简单的套路题。 ### Solution 观察到值域很小，又是求倍数，不难想到开桶统计 $a_i$，直接枚举 $a_i$ 的倍数。 记 $t_{a_i}$ 为 $a_i$ 出现次数。对 $a_i$ 排序，去重，然后枚举它的倍数 $k=j\times a_i,j\in \mathbb Z$。如果桶里有 $k$，那么答案就增加 $t_{k}\times t_{a_i}$。 看似暴力，但这显然是调和级数，时间复杂度是 $O(n\log n)$。 需要注意，统计答案时别忘了 $i\neq j,a_i=a_j$ 时，$(a_i,a_j),(a_j,a_i)$ 这**两对**都是合法的。因此这部分答案增加 $P_{t_{a_i}}^2=t_{a_i}\times(t_{a_i}-1)$。 ### Notice 如果有，请注意使用 `unique()` 前必须要 `sort()`，并更新元素数目。 ### Code ```cpp int main() { read(n);cint N=n; for(int i=1;i<=n;i++) read(a[i]); sort(a+1,a+1+n); for(int i=1;i<=n;i++) cnt[a[i]]++; n=unique(a+1,a+1+N)-a-1; for(int i=1;i<=n;i++) for(int j=a[i];j<=a[n];j+=a[i]) if(cnt[j]) { if(j!=a[i]) ans+=1ll*cnt[a[i]]*cnt[j]; else ans+=1ll*cnt[j]*(cnt[j]-1); } cout<<ans<<endl; return 0; } ```