CF1986G2 Permutation Problem (Hard Version)

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.

N/A

N/A

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.