Lời giải

Một số có đúng ba ước khi và chỉ khi nó là bình phương của một số nguyên tố: nếu ~a = p^2~ thì các ước của nó đúng bằng ~1, p, p^2~. Ngược lại, mọi số có dạng khác đều có số ước khác ~3~.

Vì ~a_i \le 10^{12}~ nên ~p \le 10^6~, hãy sàng trước các số nguyên tố đến ~10^6~.

Chú ý khi lấy căn bậc hai: sqrt trên số thực có thể sai lệch một đơn vị với các giá trị lớn, hãy kiểm tra lại bằng phép nhân số nguyên.