[HSG_HD_24] Đếm số cặp

Xem dạng PDF
Gửi bài giải
Điểm: 1,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Pascal, Python

Cho dãy số nguyên dương ~a_1, a_2, ..., a_n~.

Yêu cầu

Hãy đếm số cặp ~(i, j)~ với ~1 \le i < j \le n~ thoả mãn tính chất: Số ~a_i \times a_j~ là số chính phương (số nguyên dương ~x~ được gọi là số chính phương nếu tồn tại số nguyên ~y~ sao cho ~x = y^2~).

Dữ liệu đầu vào

Gồm hai dòng:

  • Dòng đầu tiên chứa số nguyên dương ~n~ ~(n \le 10^6)~.
  • Dòng thứ hai chứa các số nguyên ~a_1, a_2, ..., a_n~ ~(1 \le a_i \le 10^6\ \forall \ i = 1, 2, ..., n)~ cách nhau bằng dấu trống.

Dữ liệu đầu ra

Gồm một số nguyên duy nhất là số cặp tìm được

Ràng buộc dữ liệu

  • 40% số test ứng với 40% số điểm của bài có ~n \le 2000~.
  • 40% số test tiếp theo ứng với 40% số điểm của bài có ~n > 2000, a_i \le 10^4~.
  • 20% số test còn lại ứng với 20% số điểm của bài có ~n > 2000, a_i \le 10^6~.

Ví dụ

Ví dụ 1
INPUT
5
2 8 3 75 27
OUTPUT
4

Bình luận

Hãy đọc nội quy trước khi bình luận.