CF1986G1.Permutation Problem (Simple Version)

这是该问题的简化版本。唯一的区别在于本版本中 $n \leq 10^5$，且所有输入数据集合中 $n$ 的总和不超过 $10^5$。

给定一个长度为 $n$ 的排列 $p$。计算有多少对下标 $(i, j)$ 满足 $1 \leq i < j \leq n$，且 $p_i \cdot p_j$ 能被 $i \cdot j$ 整除。

排列是一个长度为 $n$ 的整数序列，其中每个整数 $1$ 到 $n$ 恰好出现一次。例如，$[1]$、$[3,5,2,1,4]$、$[1,3,2]$ 是排列，而 $[2,3,2]$、$[4,3,1]$、$[0]$ 不是排列。

每组测试数据包含多组输入。第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示输入数据的组数。接下来是每组数据的描述。

每组数据的第一行包含一个整数 $n$（$1 \leq n \leq 10^5$），表示排列 $p$ 的长度。

每组数据的第二行包含 $n$ 个两两不同的整数 $p_1, p_2, \ldots, p_n$（$1 \leq p_i \leq n$），表示排列 $p$。

保证所有输入数据集合中 $n$ 的总和不超过 $10^5$。

对于每组输入数据，输出满足条件的下标对 $(i, j)$ 的数量，其中 $1 \leq i < j \leq n$ 且 $p_i \cdot p_j$ 能被 $i \cdot j$ 整除。

对于第一组输入数据，由于排列长度为 $1$，没有下标对。

对于第二组输入数据，有一组下标对 $(1, 2)$ 满足条件。

对于第三组输入数据，下标对 $(1, 2)$ 满足条件。

对于第四组输入数据，下标对 $(1, 2)$、$(1, 5)$ 和 $(2, 5)$ 满足条件。

由 ChatGPT 4.1 翻译