1
5
2
3 6 2 2 7

1
4

在题面中，出现了一个子问题：

求出长度为 $n$ 的序列 $a$ 中有多少个有序二元组 $(i, j)$ 满足 $a_j \mid a_i$．

接下来，我们来解决这个子问题．

考虑到值域只到 $10^5$，我们考虑将值域放入数组下标，定义 $cnt[x]$ 表示序列 $a$ 中元素 $x$ 的数量，并预处理下列数据：

• $mult[x]=\sum_{y\in \{i :x\mid i \}}cnt[y]$，记录序列中是 $x$ 的倍数的数有多少个（包含 $x$）
• $divs[x]=\sum_{y\in \{i :i\mid x \}}cnt[y]$，记录序列中是 $x$ 的因数的数有多少个（包含 $x$） 这些数据可以用调和级数 $O(n\log n)$ 时间复杂度解决．

接下来，我们就可以使用 $F = \sum_{x\in\mathbb{N}} cnt[x] \times mult[x]$，来计算所有满足 $a_j \mid a_i$ 的有序二元组 $(i, j)$ 数量（包括 $i=j$）．去掉 $i=j$ 情况的方法也很简单，显然，$i=j$ 的方法有 $n$ 种，因此使用 $T = F -n$ 就可以解决上面的子问题．

那么，有序四元对的数量就是 $T^2$ 吗？显然不是．我们需要先确定一组满足子问题的有序二元对 $(i, k)$，设 $a[i] = x, a[k] = y$，由于值域小，我们可以使用枚举 $x$ 和 $y$ 的方式来确定一对数值对（此处不需要求出 $i$ 和 $j$ 具体是多少，因为后续只会用到 $a[i]$ 和 $a[j]$，因此所有 $a[i]$ 和 $a[j]$ 分别相等，但 $i,j$ 不分别相等的有序二元对是等价的），时间复杂度 $O(n\log n)$．显然，这一对数值对对应着 $cnt[x] \times cnt[y]$ 个有序二元对（如果 $x=y$ 则对应 $cnt[x]\times (cnt[x] - 1)$ 个）这些有序二元对是完全相同的，可以一起处理．

接下来，对于每一对合法的有序二元对 $(i,k)$，我们需要枚举另外一对合法的有序二元对 $(j,l)$，当然，需要满足下面这些条件：

• $a_j \mid a_l$ 且 $j\neq l$
• $j,l\notin \{i,k\}$

根据容斥原理，总方案数 $tot$ 有如下表达式：

其中：

• $T$ 为上述子问题的答案
• $A_i$ 为 $j$ 和 $l$ 中存在一个与 $i$ 相等的情况，即 $j=i$ 或 $l=i$（$j\neq l$），计算方法如下：
  • 使用 $mult[a[i]]$ 计算 $a[i]$ 的倍数有多少个，当 $a[j]$ 取到 $a[i]$ 时，$a[l]$ 的取值就一定是 $a[i]$ 的倍数，一共会有 $mult[a[i]] - 1$ 个，由于 $a[j] \neq a[l]$，所以要 -1．
  • 使用 $divs[a[i]]$ 计算 $a[i]$ 的因数有多少个，当 $a[l]$ 取到 $a[i]$ 时，$a[j]$ 的取值就一定是 $a[i]$ 的因数，一共会有 $divs[a[i]] - 1$ 个，由于 $a[j] \neq a[l]$，所以要 -1．
  • 综合一下，$A_i = mult[a[i]] + divs[a[i]] - 2$．
• $A_k$ 为 $j$ 和 $l$ 中存在一个与 $k$ 相等的情况，即 $j=k$ 或 $l=k$（$j\neq l$），计算方法同上．
• $B_{ik}$ $j$ 和 $l$ 中一个与 $i$ 相等，另一个与 $k$ 相等的情况，即 $j=i$ 且 $l=k$；或 $j=k$ 且 $l=i$
  • 对于 $j=i$ 且 $l=k$ 的情况，由于 $a_i \mid a_k$，故 $a_j \mid a_l$ 恒成立，因此，这种情况一定会有一个贡献为 1．
  • 对于 $j=k$ 且 $l=i$ 的情况，由于 $a_i \mid a_k$，当且仅当 $a_j=a_l$ 时， $a_j \mid a_l$ 成立，故当 $a_j=a_l$ 时贡献为 1，否则贡献为 0．

得出 $tot$ 之后，数值对 $(x,y)$ 对答案的贡献就是这个数值对对应的有序二元组数量和 $tot$ 之积，具体来说，

• 若 $x=y$，贡献为 $cnt[x] * (cnt[x] - 1) * tot$．
• 否则，贡献为 $cnt[x] * cnt[y] * tot$．

注意，这个题需要开 __int128．

标程

1
#include <bits/stdc++.h>
2
using namespace std;
3
typedef __int128 lll;
4
const int N = 1e5 + 100;
5
int n, a[N];
6
lll cnt[N], mult[N], divs[N];
7

8
void print(lll x) {
9
    if (x >= 10)
10
        print(x / 10);
11
    putchar('0' + x % 10);
12
}
13

14
signed main() {
15
    cin >> n;
16
    int maxa = -1;
17
    for (int i = 1; i <= n; i++) {
18
        cin >> a[i];
19
        cnt[a[i]]++;
20
        maxa = max(maxa, a[i]);
21
    }
22
    // 预处理
23
    for (int i = 1; i <= maxa; i++) {
24
        for (int j = i; j <= maxa; j += i) {
25
            mult[i] += cnt[j];
26
        }
27
        for (int j = 1; j <= sqrt(i); j++) {
28
            if (i % j)
29
                continue;
30
            divs[i] += cnt[j];
31
            if (j * j != i) {
32
                divs[i] += cnt[i / j];
33
            }
34
        }
35
    }
36
    lll T = -n;
37
    for (int i = 1; i <= maxa; i++) {
38
        T += cnt[i] * mult[i];
39
    }
40
    // 计算贡献
41
    lll ans = 0;
42
    for (int x = 1; x <= maxa; x++) {
43
        for (int y = x; y <= maxa; y += x) {
44
            lll Ai = mult[x] + divs[x] - 2;
45
            lll Ak = mult[y] + divs[y] - 2;
46
            lll Bik = 1 + (x == y);
47
            lll tot = T - Ai - Ak + Bik;
48
            if (x == y) {
49
                ans += (lll)cnt[x] * (cnt[y] - 1) * tot;
50
            } else {
51
                ans += (lll)cnt[x] * cnt[y] * tot;
52
            }
53
        }
54
    }
55
    print(ans);
56
}