Subtask 1

Duyệt trâu tất cả những cặp $(a_i,a_j)$ trong mảng $a$, để kiểm tra một số có phải là chính phương, ta có thể dùng hàm sqrt() hoặc chặt nhị phân.

ĐPT: $O(n^2)$

Subtask 2

Vì $a_i\le {10}^3$, nên thay vì duyệt chỉ số $(i,j)$ thì ta duyệt theo giá trị.

Gọi $cn{t}_u$ là số lần xuất hiện của giá trị $u$ trong mảng, $M$ là giá trị lớn nhất trong mảng, khi đó đáp án sẽ là $\sum _{i=1}^M\sum _{j=i}^{M}cn{t}_i\cdot cn{t}_j$ nếu $i+j\le k$ và $i\cdot j$ là số chính phương.

ĐPT: $O(M^2)$ với $M$ là giá trị lớn nhất trong mảng.

Sutbask 3

Ta xét tích của hai số $x$ và $y$ bất kì, đặt $z=x\cdot y$.

Giả sử $x$ và $y$ có dạng phân tích thừa số nguyên tố như sau:

$x=p_1^{a_1}\cdot p_2^{a_2}\cdots p_m^{a_m}$.

$y=p_1^{b_1}\cdot p_2^{b_2}\cdots p_m^{b_m}$.

($a_i,b_i\ge 0$, $p_i$ là số nguyên tố).

Khi đó: $z=p_1^{a_1+b_1}\cdot p_2^{a_2+b_2}\cdots p_m^{a_m+b_m}$.

Để $z$ là số chính phương, thì $a_i+b_i\equiv 0\mathrm{mod}2(\mathrm{\forall }1\le i\le m)$.

Từ đó suy ra được: $a_i\equiv b_i\mathrm{mod}2$.

Như vậy, ta xét dạng "nén" của một số $x$ như sau: $g(x)=p_1^{a_1\mathrm{mod}2}\cdot p_2^{a_2\mathrm{mod}2}\cdots p_m^{a_m\mathrm{mod}2}$.

Để $x\cdot y$ là số chính phương thì: $g(x)=g(y)$.

Như vậy ta chỉ cần xét những cặp $x$ có cùng giá trị $g(x)$, xong rồi chặt nhị phân để tìm những cặp thỏa mãn $\le k$.

Để phân tích $x$ thành thừa số nguyên tố, ta có thể xử lý giống như cách kiểm tra số nguyên tố.

ĐPT: $O((n+M)\log M)$ với $M$ là giá trị lớn nhất trong mảng.