这是问题的困难版本。唯一的区别是,在此版本中 $$$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
6 1 1 2 1 2 3 2 3 1 5 2 4 1 3 5 12 8 9 7 12 1 10 6 3 2 4 11 5 15 1 2 4 6 8 10 12 14 3 9 15 5 7 11 13
输出 #1
0 1 1 3 9 3
注意
在第一组输入数据中,没有索引对,因为排列的大小为 $$$1$$$。
在第二组输入数据中,有一个索引对 $$$(1, 2)$$$ 并且有效。
在第三组输入数据中,索引对 $$$(1, 2)$$$ 有效。
在第四组输入数据中,索引对$$$(1, 2)$$$、$$$(1, 5)$$$和$$$(2, 5)$$$是有效的。