题目大意

给定 $n$ 个正整数 $a_1, a_2, \ldots, a_n$，求有多少个有序数对 $(i, j)$ 满足：

• $1 \le i \le n$，$1 \le j \le n$
• $i \ne j$
• $a_i$ 是 $a_j$ 的倍数（即 $a_j \mid a_i$）

样例分析

样例 1

输入：
6
16 11 6 1 9 11

输出：
7

解释：

• $(1,6)$：$16$ 是 $1$ 的倍数
• $(3,6)$：$6$ 是 $1$ 的倍数
• $(5,6)$：$9$ 是 $1$ 的倍数
• $(2,6)$：$11$ 是 $1$ 的倍数
• $(4,6)$：$11$ 是 $1$ 的倍数
• $(1,3)$：$16$ 是 $6$ 的倍数
• $(1,5)$：$16$ 是 $9$ 的倍数

共 $7$ 个有效数对。

算法思路

暴力解法（40分）

直接枚举所有 $i \ne j$ 的数对，检查 $a_i$ 是否是 $a_j$ 的倍数。

• 时间复杂度：$O(n^2)$
• 空间复杂度：$O(n)$

优化解法（100分）

核心思想

使用频次统计和倍数枚举来优化：

1. 频次统计：用数组 $\text{freq}[x]$ 记录数值 $x$ 在序列中出现的次数
2. 倍数枚举：对于每个数 $a_i$，枚举它的所有倍数 $k \times a_i$，统计这些倍数在序列中出现的总次数
3. 答案计算：对于 $a_i$，它能作为倍数的数对数量为所有 $k \times a_i$ 出现次数之和减 $1$（减去自身）

算法步骤

1. 读入数据，找到最大值 $\text{max}_a$
2. 统计每个数值的出现频次 $\text{freq}[]$
3. 对于每个 $a_i$：
   • 枚举所有倍数：$a_i, 2a_i, 3a_i, \ldots, \lfloor \frac{\text{max}_a}{a_i} \rfloor \times a_i$
   • 累加这些倍数出现的次数 $\text{sum\_valid}$
   • 答案增加 $\text{sum\_valid} - 1$（减去自身）

时间复杂度

• 频次统计：$O(n)$
• 倍数枚举：对于每个 $a_i$，需要枚举 $\lfloor \frac{\text{max}_a}{a_i} \rfloor$ 次
• 总复杂度：$O(n + \sum\limits_{i=1}^n \frac{\text{max}_a}{a_i})$
• 最坏情况下约为 $O(n + \text{max}_a \log \text{max}_a)$，可以接受

空间复杂度

• $O(\text{max}_a)$，用于存储频次数组

关键点说明

1. 去重处理

在统计每个 $a_i$ 的倍数时，需要减去自身出现的次数，因为题目要求 $i \ne j$。

2. 数值范围

• $n \leq 2 \times 10^5$
• $a_i \leq 5 \times 10^5$
• 频次数组大小：$5 \times 10^5$

3. 边界情况

• 当 $a_i = 1$ 时，需要枚举所有数，但频次统计保证了效率
• 重复数值需要正确计数

算法优势

1. 避免重复计算：通过频次统计，相同数值只需计算一次倍数关系
2. 利用数值范围：$\text{max}_a$ 有限，倍数枚举在可控范围内
3. 简单高效：代码实现简洁，易于理解和调试

算法标签

• 数学
• 计数
• 倍数枚举
• 频次统计

总结

本题通过将问题转化为频次统计和倍数枚举，巧妙地避免了 $O(n^2)$ 的暴力枚举，在给定的数据范围内能够高效求解。核心在于发现数值范围的有限性，从而使用空间换时间的策略。