Count number of pairs of elements whose product is a perfect square
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.