G1. 排列问题（简单版） – 详细题解

问题重述

给定一个 $1$ 到 $n$ 的排列 $p$，求有多少对 $(i, j)$（$1 \le i < j \le n$）满足 $p_i \cdot p_j$ 能被 $i \cdot j$ 整除。

关键转化

条件 $i \cdot j \mid p_i \cdot p_j$ 等价于

$$\frac{p_i}{i} \cdot \frac{p_j}{j} \text{ 是整数？不准确，因为公因子会约分。正确方式：引入最大公因数。 $$

设 $g_i = \gcd(i, p_i)$，令

$$x_i = \frac{p_i}{g_i}, \quad y_i = \frac{i}{g_i}.$$

注意 $x_i$ 与 $y_i$ 互质（因为除去了最大公因数）。那么条件 $i j \mid p_i p_j$ 可改写为：

$$\frac{p_i p_j}{i j} = \frac{x_i g_i \cdot x_j g_j}{y_i g_i \cdot y_j g_j} = \frac{x_i x_j}{y_i y_j}. $$

由于 $x_i$ 与 $y_i$ 互质，$x_j$ 与 $y_j$ 互质，故分数 $\frac{x_i x_j}{y_i y_j}$ 为整数当且仅当分母的每个素因子都能被分子约去。因为 $x_i$ 与 $y_i$ 无公共因子，所以 $y_i$ 必须整除 $x_j$，且 $y_j$ 必须整除 $x_i$。即

$$y_i \mid x_j \quad \text{且} \quad y_j \mid x_i.$$

因此，每对 $(i,j)$ 满足条件等价于：

$$\frac{p_i}{\gcd(i,p_i)} \text{ 是 } \frac{j}{\gcd(j,p_j)} \text{ 的倍数，且反过来也成立？实际上双向条件可简化为：} y_i \mid x_j \text{ 且 } y_j \mid x_i. $$

进一步简化

由于 $x_i = \frac{p_i}{g_i}$ 与 $y_i = \frac{i}{g_i}$ 互质，且 $p_i \le n$，$i \le n$，所以所有 $x_i$ 和 $y_i$ 都是不超过 $n$ 的整数。条件 $y_i \mid x_j$ 表明 $x_j$ 是 $y_i$ 的倍数。我们想要统计所有无序对 $(i, j)$ 满足双向整除关系。注意到若 $y_i \mid x_j$ 且 $y_j \mid x_i$，则两个方向必须同时成立。我们可以将每个下标 $i$ 映射到一对互质的数 $(x_i, y_i)$，然后计数满足 $y_i \mid x_j$ 且 $y_j \mid x_i$ 的对数。

一种经典处理是枚举所有可能的 $(x,y)$ 对，但 $x,y$ 的取值范围都是 $O(n)$，直接枚举 $O(n^2)$ 不可行。代码中使用了根号分治技巧：

• 对于每个 $i$，我们得到 $a_i = x_i$，$b_i = y_i$。
• 条件变为：$b_i \mid a_j$ 且 $b_j \mid a_i$。

算法思路

我们采用离线处理，从大到小遍历 $i$，并维护已经处理过的 $j$（即 $j > i$ 或反过来）。在代码中，从 $n$ 向下扫描，每次查询当前 $i$ 与所有已处理（即更大下标）的 $j$ 的配对情况。

对于当前 $i$，我们需要统计已处理的下标 $j$ 中满足 $b_i \mid a_j$ 且 $b_j \mid a_i$ 的个数。由于我们按 $i$ 递减处理，已处理的 $j$ 都大于当前 $i$，而 $(i,j)$ 无序对只需统计一次。

利用 $b_j \mid a_i$ 枚举因子

条件 $b_j \mid a_i$ 意味着 $b_j$ 是 $a_i$ 的因子。同时 $b_i \mid a_j$ 意味着 $a_j$ 是 $b_i$ 的倍数。因此，对于固定的 $i$，我们可以枚举 $a_i$ 的所有因子 $d$，然后考虑所有满足 $b_j = d$ 的那些 $j$，且还要满足 $b_i \mid a_j$。此时 $a_j$ 必须是 $b_i$ 的倍数。所以我们需要在已处理的 $j$ 中，对每个因子 $d$，统计有多少个 $j$ 满足 $b_j = d$ 且 $a_j$ 是 $b_i$ 的倍数。

根号分治

直接维护所有 $(b_j, a_j)$ 对，并对于每个 $i$ 枚举因子 $d$（$O(\sqrt{a_i})$ 个），然后查询 $b_i$ 的倍数，这需要能够快速回答：对于给定的 $b$ 和 $d$，有多少个 $j$ 使得 $b_j = d$ 且 $a_j$ 是 $b$ 的倍数。我们可以预先将 $b_j$ 按值分类，对于出现次数较少的 $b$（小类），直接存储其所有 $a_j$ 的列表，查询时遍历该列表检查 $b_i$ 是否整除 $a_j$。对于出现次数很多的 $b$（大类），则维护一个数组 $cnt[d][m]$ 表示对于该 $b$ 值，$a$ 值为 $m$ 的个数，并对倍数累加预处理？代码中采用的方法：

• 设定阈值 $B = \sqrt{n}$（大约 350）。
• 对于出现次数 $\le B$ 的 $b$ 值，将其视为“小 $b$”，我们直接存储所有对应的 $a$ 值列表。查询时，对于每个因子 $d$，若 $d$ 是小 $b$，则遍历其列表，检查 $b_i \mid a_j$。
• 对于出现次数 $> B$ 的 $b$ 值，将其视为“大 $b$”，我们为每个大 $b$ 维护一个长度为 $n$ 的数组 $f$，其中 $f[x]$ 表示当前已处理的 $j$ 中，满足 $b_j = b$ 且 $a_j = x$ 的数量。然后，为了快速回答 $b_i$ 的倍数，我们可以通过对倍数累加：对每个大 $b$，我们维护一个额外的数组 $g[y] = \sum_{b_i \mid a_j} f[a_j]$，但这里 $b_i$ 是变量，所以每次查询需要枚举 $b_i$ 的倍数 $t$，将 $f[t]$ 求和。由于 $b_i$ 也是 $O(n)$，但 $b_i$ 的倍数个数约 $n / b_i$，当 $b_i$ 较小时可能很多。但代码中采用了另一种策略：在查询时，遍历 $b_i$ 的倍数 $mul$，然后对于每个大 $b$，直接累加其数组中的 $f[mul]$。由于大 $b$ 个数很少（最多 $n/B$），而 $b_i$ 的倍数个数最多 $n$，但总复杂度可控。

实际上，代码实现如下：

• 预处理所有数的因子列表 divs。
• 对每个下标 $i$，计算 $g = \gcd(i, p_i)$，$a[i] = p_i / g$，$b[i] = i / g$。
• 统计每个 $b$ 出现的次数 cnt_b。
• 标记大 $b$（出现次数 > B），并为其分配一个 ID，同时准备一个二维数组 big[id] 用于计数 $a$ 值（大小 $n+1$）。
• 对于小 $b$，用一个 vector 列表存储每个小 $b$ 对应的所有 $a$ 值。
• 从 $i = n$ 向下遍历：
  • 查询：枚举 $a[i]$ 的所有因子 $d$（这些 $d$ 就是候选的 $b_j$）。对于每个 $d$：
    • 如果 $d$ 是大 $b$，则获取其 ID，然后枚举 $b[i]$ 的所有倍数 $mul$，将 big[id][mul] 累加到答案。
    • 如果 $d$ 是小 $b$，则遍历该 $d$ 对应的 $a$ 值列表 $vec$，统计有多少个 $a_j$ 能被 $b[i]$ 整除。
  • 注意：这里遍历 $b[i]$ 的倍数时，要确保 $j > i$，但因为我们是从大到小插入，所以目前 $big$ 和 $small$ 中只包含已经处理过的 $j$（即下标大于当前 $i$ 的），所以正确。
  • 最后将当前 $(a[i], b[i])$ 插入到对应的数据结构中：如果 $b[i]$ 是大 $b$，则 big[id][a[i]]++；否则将 $a[i]$ 加入到 small[b[i]] 列表中。

最终输出答案即可。

复杂度分析

• 预处理因子：$O(n \log n)$。
• 计算 $a_i,b_i$：$O(n)$。
• 根号分治：每个 $i$ 枚举因子个数 $O(\sqrt{a_i})$，对于每个因子 $d$，若 $d$ 是大 $b$，则枚举 $b_i$ 的倍数，总数约为 $n/1 + n/2 + ... = O(n \log n)$ 但只发生在 $d$ 是大 $b$ 时，由于大 $b$ 个数少，实际总复杂度 $O(n \sqrt{n})$ 可接受（$n \le 10^5$）。若 $d$ 是小 $b$，则遍历其列表，每个元素在被遍历时只属于它作为 $d$ 的情况，且每个元素最多被遍历 $\sqrt{n}$ 次？其实每个小 $b$ 的列表长度不超过 $B$，而每个 $i$ 的因子个数 $O(\sqrt{n})$，所以总复杂度 $O(n \sqrt{n})$。

由于 $\sum n \le 10^5$，该算法足够快。

总结

本题的关键在于将整除条件转化为互质因子关系，进而导出 $b_i \mid a_j$ 且 $b_j \mid a_i$。然后通过根号分治平衡小频率和大频率的查询，利用因子枚举和倍数枚举高效统计满足条件的数对。代码实现中细节处理较多，但整体思路清晰，时间复杂度可接受。