Consider the following problem (phrased with the use of a black box).
You choose $n$ numbers $X = \{x_1,\ldots,x_n\}$ and pass it to a black box that returns a list $Y = \{y_1,\ldots,y_m\}$ where each of the elements is a product of the elements of some $k-subset$ of $X$. That is for every $1 \leq i \leq m$ the black box picks an element $ Y_i \in {X \choose k}$ and sets $y_i = \prod_{p \in Y_i} p.$
Given that I am able to choose the elements of $X$ I am wondering how should I pick them in order to be able to compute the number of intersecting $(Y_i,Y_j)$ pairs as efficiently as possible.
One thing is take $X$ to contain only pairwise coprime elements and then check the if the pairs $(y_i,y_j)$ are coprime or not.
I am wondering, if there is something even more slicker that can be done that would then allow to compute the number of intersecting pairs in say $O(m)$ or at least faster than $O(m^2)$?