How can I efficiently calculate the number of quadruples in an array whose product is a perfect cube?
For example, if the array is [1, 2, 2, 4, 4], then the result should be 1, because that array has only one such quadruple: 2 · 2 · 4 · 4 = 64 = 43.
Length of array is 10^5 :)
Numbers can be duplicate and in lots of amount. Yes,prime-factorization for each number is available :-)
The question comes down to finding quadruples in $\mathbb{F}_3^n$ that sum to $0$, where $n$ is the number of prime factors that appear in any of the numbers. This seems to be a linear algebra problem, so probably the fastest solution is some linear algebra solution.
I will present one that may not be the fastest, but is rather interesting. For each prime $p_i$ dividing the number, we correspond a variable $x_i$. Then we take the product over all numbers in your array of $(1+x\cdot x_1^{e_{i, 1}}x_2^{e_{i, 2}}\ldots x_n^{e_{i, n}})$ where $e_{i, j}$ is the power of $p_i$ in the $j$'th number $\mod 3$. For example, in your array it would be $(1+x)(1+x\cdot x_1)^2(1+x\cdot x_1^2)^2$.
Then you evaluate this at all combinations of $x_i$ being in the set $\{1, \omega_3, \omega_3^2\}$ where $\omega_3$ is a third root of unity, and you add these all up and divide by $3^n$. For example, in your situation, we'd get $\frac{(1+x)^5+(1+x)(1+\omega_3 x)^2(1+\omega_3^2 x)^2+(1+x)(1+\omega_3^2x)^2(1+\omega_3x)^2}{3}=1+x+4x^2+4x^3+x^4+x^5$. The coefficient of $x^4$ tells you the number.
In another example, you could take the list $[1, 2, 3, 4, 6, 9, 12, 18, 36]$. Your polynomial would be (replacing $x_1$ with $y$ and $x_2$ with $z$)
$(1+x)(1+xy)(1+xy^2)(1+xz)(1+xyz)(1+xy^2z)(1+xz^2)(1+xyz^2)(1+xy^2z^2)$.
Replacing $y, z$ with $1, \omega_3$ and $\omega_3^2$, adding, and dividing by $9$ gives
$1 + x + 4 x^2 + 12 x^3 + 14 x^4 + 14 x^5 + 12 x^6 + 4 x^7 + x^8 + x^9$
whose coefficient of $x^4$ is $14$, which is the answer. And the coefficients of the other powers are the solutions for triples, quintuples, etc.