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 \leq 10^3~, nên thay vì duyệt chỉ số ~(i, j)~ thì ta duyệt theo giá trị.

Gọi ~cnt_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} cnt_i \cdot cnt_j~ nếu ~i + j \leq 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 \geq 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 \mod 2 \: (\forall 1 \leq i \leq m)~.

Từ đó suy ra được: ~a_i \equiv b_i \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 \mod 2} \cdot p_2 ^ {a_2 \mod 2} \cdots p_m ^ {a_m \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 ~\leq 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.