Bài tập về nhà
Xem PDF
Điểm:
1700 (p)
Thời gian:
0.5s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Sau một ngày sinh nhật mệt mỏi, quyết định leo lên giường để đi ngủ. Bỗng cậu chợt nhớ ra mình vẫn chưa làm bài tập về nhà của lớp Coding 69420 dành cho trẻ sơ sinh. Cậu liền bật dậy và làm nhưng bài lại quá khó đối với cậu.
Nội dung bài
Trong một dãy \(a\) gồm \(n\) phần tử, một cặp \((i, j)\) được gọi là cặp số chính phương nếu nó thỏa mãn:
- \(1 \le i < j \le n\).
- \(a_i \times a_j\) là một số chính phương.
Cho dãy \(a\) gồm \(n\) phần tử, hãy đếm số lượng cặp số chính phương \((i, j)\) của dãy \(a\).
Một bài dành cho trẻ sơ sinh như vậy mà giải cũng không được, bạn hãy giúp cậu ấy nhé.
Input, Output and Subtask
Input
- Số nguyên dương \(n\) \((2 \le n \le 10^5)\).
- Dãy \(a\) gồm \(n\) phần tử \(a_1, a_2, ..., a_n\) \((1 \le a_i \le 10^6)\).
Output
- In ra kết quả thỏa mãn.
Scoring
- Subtask \(1\) \((30\%)\): \(2 \le n \le 10^3\).
- Subtask \(2\) \((70\%)\): Không giới hạn gì thêm.
Example
Input
6
4 8 2 9 2 4
Output
6
Note
- Có tổng cộng \(6\) cặp số chính phương \((i, j)\) là \((1, 4), (1, 6), (2, 3), (2, 5), (3, 5), (4, 6)\).
Bình luận