Count number of pairs of elements whose product is a perfect square Given two arrays whose elements lie between $[1,10^5]$ and the size of arrays is $[1,10^5]$, how can we find the total number of pairs of elements from these arrays such that their product is a perfect square? The arrays may have same elements.

For example:


  Array 1: {1, 2, 4, 5}
  
  Array 2: {4, 8, 16, 125}
  
  Output : 6


The pairs are (1, 4), (1, 16), (2, 8), (4, 4), (4, 16), (5, 125).

If the array size is $10^5$, an $n^2$ algorithm would be inefficient.
There are $9592$ primes below $10^5$. You can convert each number in each array to a sparse binary vector of length $9592$, signifying the parity of the power of each prime. Using radix sort, sort each of the arrays, and then merge them. Denoting by $a_x,b_x$ the number of times that $x$ appears in each of the arrays (respectively), the answer is $\sum_x a_x b_x$.

There are many optimizations possible for this general scheme, which in practice can speed it up significantly. I'll let you work them out.