Это сложная версия задачи. Единственное различие состоит в том, что в этой версии \(n \leq 5 \cdot 10^5\) и сумма \(n\) по всем наборам входных данных не превосходит \(5 \cdot 10^5\).
Вам дана перестановка \(p\) длины \(n\). Посчитайте количество пар индексов \(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]\) — нет.
Выходные данные
Для каждого набора входных данных выведите количество пар индексов \(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)\).
Примеры
| № | Входные данные | Выходные данные |
|
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
|
0
1
1
3
9
3
|