数学问题
SpeedStar
·
·
个人记录
对于长度为 n 的序列 a，对于 1 \leqslant i < j \leqslant n，若不存在 a_k |a_i 且 a_k | a_j，那么 (i, j) 是好的。求出 a 的好的数对数量。
限制：
-
1 \leqslant n \leqslant 10^6
-
1 \leqslant a_i \leqslant 10^6
算法分析
设 $\begin{cases}
0, & \exists \, i \in [1, n] \Rightarrow \, a_i | d\
1, & \text{其他}
\end{cases}
则好对数量为：
$$
\sum_{i=1}^{n}\sum_{j+1}^n f(\gcd(a_i, a_j)) = \sum_{d=1}^n f(d) \sum_{i=1}^n\sum_{j=i+1}^n [\gcd(a_i, a_j) = d]
$$
对于 $f(d)$ 和 $\displaystyle \sum_{i=1}^n\sum_{j=i+1}^n [\gcd(a_i, a_j) = d]$ 显然可以在 $O(n\log n)$ 的时间预处理出来
```cpp
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 1; i <= (n); ++i)
using namespace std;
using ll = long long;
const int M = 1000005;
int f[M], cnt[M];
ll dp[M];
ll c2(ll n) { return n*(n-1)/2; }
int main() {
int n;
cin >> n;
rep(i, n) {
int a; cin >> a;
cnt[a]++;
f[i] = 1;
}
rep(i, n) if (cnt[i]) {
for (int j = i; j <= n; j += i) {
f[j] = 0;
}
}
rep(i, n) {
for (int j = i*2; j <= n; j += i) {
cnt[i] += cnt[j];
}
}
ll ans = 0;
for (int i = n; i >= 1; --i) {
if (!cnt[i]) continue;
dp[i] = c2(cnt[i]); // gcd >= i的数对个数
for (int j = i*2; j <= n; j += i) {
dp[i] -= dp[j];
}
ans += f[i]*dp[i];
}
cout << ans << '\n';
return 0;
}
```