Cặp số chính phương

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
flo
Dạng bài
Ngôn ngữ cho phép
C++, Clang, Clang++, Cobol, D, Groovy, Haskell, JS, Lua, Node JS, ObjectiveC, Pascal, Prolog, Pypy 3, Python, Scala
Điểm: 1700 (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