Permutation Problem (Hard Version)
Contest: Codeforces Round 954 (Div. 3)
Difficulty rating: 2500
Tags: brute force, data structures, hashing, math, number theory

This is the hard version of the problem. The only difference is that in this version $$$n \leq 5 \cdot 10^5$$$ and the sum of $$$n$$$ for all sets of input data does not exceed $$$5 \cdot 10^5$$$.

You are given a permutation $$$p$$$ of length $$$n$$$. Calculate the number of index pairs $$$1 \leq i < j \leq n$$$ such that $$$p_i \cdot p_j$$$ is divisible by $$$i \cdot j$$$ without remainder.

A permutation is a sequence of $$$n$$$ integers, in which each integer from $$$1$$$ to $$$n$$$ occurs exactly once. For example, $$$[1]$$$, $$$[3,5,2,1,4]$$$, $$$[1,3,2]$$$ are permutations, while $$$[2,3,2]$$$, $$$[4,3,1]$$$, $$$[0]$$$ are not.

Input format:
Each test consists of several sets of input data. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of sets of input data. Then follows their description.

The first line of each set of input data contains a single integer $$$n$$$ ($$$1 \leq n \leq 5 \cdot 10^5$$$) — the length of the permutation $$$p$$$.

The second line of each set of input data contains $$$n$$$ distinct integers $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \leq p_i \leq n$$$) — the permutation $$$p$$$.

It is guaranteed that the sum of $$$n$$$ for all sets of input data does not exceed $$$5 \cdot 10^5$$$.

Output format:
For each set of input data, output the number of index pairs $$$1 \leq i < j \leq n$$$ such that $$$p_i \cdot p_j$$$ is divisible by $$$i \cdot j$$$ without remainder.

Constraints:
Time limit: 3.0 s
Memory limit: 128.0 MB

Note:
In the first set of input data, there are no index pairs, as the size of the permutation is $$$1$$$.

In the second set of input data, there is one index pair $$$(1, 2)$$$ and it is valid.

In the third set of input data, the index pair $$$(1, 2)$$$ is valid.

In the fourth set of input data, the index pairs $$$(1, 2)$$$, $$$(1, 5)$$$, and $$$(2, 5)$$$ are valid.

Example input:
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

Example output:
0
1
1
3
9
3

Editorial:
Let $$$a_i = \frac{p_i}{\gcd(i, p_i)}$$$, $$$b_i = \frac{i}{\gcd(i, p_i)}$$$. Notice that we want to calculate the number of index pairs $$$i < j$$$, such that:
• $$$a_j$$$ is divisible by $$$b_i$$$.
• $$$a_i$$$ is divisible by $$$b_j$$$.
Let's iterate through the values of $$$b_i$$$ from $$$1$$$ to $$$n$$$ (note that we are not fixing the element $$$i$$$, but rather fixing the value of $$$b_i$$$). Now we know that we are interested in all $$$a_j = b_i \cdot k$$$, for some positive integer $$$k$$$. Let's iterate through all such possible $$$a_j$$$, and then iterate through all pairs with that value of $$$a_j$$$. Add all suitable $$$b_j$$$ to the count array.
Now, for a fixed $$$b_i$$$ and the constructed count array for it, iterate through all $$$a_i$$$ that exist with this $$$b_i$$$. We can iterate through all divisors of $$$a_i$$$ and simply add their count from the count array to the answer, because:
• Only those pairs for which $$$a_j$$$ is divisible by $$$b_i$$$ are considered in the count array, so we have accounted for the first condition.
• We have accounted for the second condition when iterating through the divisors of $$$a_i$$$.
If the above is implemented correctly, a solution can be obtained in $$$O(n \log n)$$$. For this, we will need to pre-calculate all divisors for each $$$i$$$ from $$$1$$$ to $$$n$$$. We can iterate through $$$i$$$ and mark it as a divisor for all numbers of the form $$$k \cdot i$$$.
Also, everything written above works in $$$O(n \log n)$$$, because: the array $$$a$$$ was obtained from a permutation by dividing some elements, so the total number of divisors of all elements in $$$a$$$ (as well as the array $$$b$$$) is no more than the total number of divisors of numbers from $$$1$$$ to $$$n$$$. And the total number of divisors of numbers from $$$1$$$ to $$$n$$$ is at most $$$\sum\limits_{i=1}^n \frac{n}{i} = O(n \log n)$$$.