CF1986G2.Permutation Problem (Hard Version)

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

给定一个长度为 $n$ 的排列 $p$。计算有多少对下标 $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 5 \cdot 10^5$），表示排列 $p$ 的长度。

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

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

对于每组输入数据，输出满足条件的下标对 $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 翻译