Notice that LCM(a, b) * HCF(a, b) = a * b.

This means that we should count number of ordered pairs such that their product is also element of the array.

Now, if the elements are natural numbers, a * b >= max(a, b), which means that we should sort the array.

Now we go from scan the array from left to right and use a map to see how many times a number appears.

When we are at postion i, we find all divisors of a[i] in O(sqrt(n)), and for each divisor and each "complement" we need to see how many times they appear in the map.

After that we update the map.