Let's work on $v_p(a_i)=t(i)_p$ for any $p|a_t$ for some $t$ Define $C=\left\{ (i;j)|\leq 1i<j\leq n,a_ia_j=c^3\right\}$ Case 1: Exist $t(i)_p \vdots 3$ for some $i,p$ Then if products of $a_i$ with some $a_t$ is a cube then $t(j)_p \vdots 3$ and $\frac{a_ia_j}{p^{t(i)_p+t(j)_p}}$ is a cube So we can assume there is no $t(i)_p \vdots 3$ So So now let's do with case 2: Case 2: There is no $t(i)_p \vdots 3$ for some $i,p$ Works: For any $p$, define $A_j=\left\{ i||t(i)_p\equiv j \, \, (mod\, \, 3)\right\}$ Then $|C| \leq |A_1||A_2| \leq \frac{(|A_1|+|A_2|)^{2}}{4}\leq \frac{n^2}{4}$ Equality happen when there is $n/2$ $a_i$ is 3k+1-th power of a prime, and the others is 3k+2-th power of that prime

Consider a graph with label $a_1,\dots,a_n$ on each vertex and there exists and edge between $a_i,a_j$ iff $a_ia_j$ is cube. Since none of $a_1,\dots,a_n$ is cube, edges can't form a triangle $a_i,a_j,a_k$ otherwise $a_i=\frac{a_i^3\cdot(a_ja_k)}{(a_ia_j)\cdot(a_ia_k)}$ is a cube. The rest is followed by Turan's Theorem.