Cặp số chính phương
Xem PDF
Điểm:
1400 (p)
Thời gian:
0.5s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
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\).
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 (11)