Требуется посчитать количество троек чисел $$$a$$$, $$$b$$$ и $$$c$$$ ($$$1 \le a < b < c \le n$$$), таких что $$$a \cdot b$$$, $$$a \cdot c$$$ и $$$b \cdot c$$$ — квадраты натуральных чисел.
Рассмотрим разложение числа $$$x$$$ на простые множители в виде $$$x = p_1^{q_1} \cdot p_2^{q_2} \cdot \dots \cdot p_k^{q_k}$$$. Заметим, что $$$a \cdot b$$$ является квадратом натурального числа, если в разложении числа $$$a \cdot b$$$ все $$$q_i$$$ — четны. Значит, в разложениях $$$a$$$ и $$$b$$$ множества простых чисел, входящих в нечетной степени, должны совпадать.
Таким образом, найдем для каждого числа $$$x$$$ от $$$1$$$ до $$$n$$$ множество простых, которые входят в $$$x$$$ в нечетной степени. После этого, разобьем числа на группы с совпадающими множествами. Ответом является сумма по всем группам, количество способов выбрать три числа в группе. Количество способов выбрать три числа из $$$m$$$ штук равно $$$\frac{m \cdot (m - 1) \cdot (m - 2)}{6}$$$.