https://www.luogu.com.cn/problem/P7517
给定长度为 \(n\) 的数组 \(a_i\)，统计数对 \((i, j)\) 个数，满足 \(i \ne j\) 且 \(a_j \mathop | a_i\)。
\(2 \le n \le 5 \times 10^5\)，\(1 \le a_i \le 5 \times 10^5\)。
答案和数组顺序无关，一种处理方式是将原数组转化成权值数组 \(b\) 做，还有一种是将原数组排序。
这里发现当成权值数组做会更好做。而且因为 \(1 \le a_i \le 5 \times 10^5\)，转权值数组可以不需离散化。
设原数组值域，即权值数组值域为 \(V\)，则答案是
\[\sum_{i = 1}^V b_i \times (b_i - 1) + \sum_{j = 2}^{i \times j \le V}b_i \times b_j
\]
统计可以做到 \(V \log V\)，可以通过此题。
另外不枚举倍数，而是枚举因数，能做到 \(V^{1.5}\)，也能过。注意 long long。
#define int long long
const int maxa = (int)5e5 + 5;
int b[maxa];
signed main() {
int n = read();
for (int i = 1; i <= n; ++i)
++b[read()];
int ans = 0;
const int m = (int)5e5;
for (int i = 1; i <= m; ++i) {
for (int j = i * 2; j <= m; j += i)
ans += b[i] * b[j];
ans += b[i] * (b[i] - 1);
}
printf("%lld\n", ans);
return 0;
}