Bài 1. Cặp số

Cho một dãy số nguyên dương a = (a_1, a_2, ..., a_n). Hãy đếm số lượng cặp chỉ số (i, j) thỏa mãn: 1 <= i < j <= n và LCM(a_i, a_j) / GCD(a_i, a_j) là một số chính phương.

Trong đó:

• LCM(a_i, a_j) là bội chung nhỏ nhất của a_i và a_j.
• GCD(a_i, a_j) là ước chung lớn nhất của a_i và a_j.
• Số chính phương là một số nguyên bằng bình phương của một số nguyên.

Đầu vào:

• Dòng đầu tiên chứa một số nguyên dương n (1 <= n <= 10^6).
• Dòng thứ hai chứa n số nguyên a_1, a_2, ..., a_n (1 <= a_i <= 10^6).

Đầu ra:

• In ra một số nguyên duy nhất là số lượng cặp chỉ số (i, j) thỏa mãn yêu cầu.

Ràng buộc

• 1 <= n <= 10^6
• 1 <= a_i <= 10^6 với mọi 1 <= i <= n

Subtask (tham khảo)

• Subtask 1 (20% số điểm): n <= 1000.
• Subtask 2 (20% số điểm): Tất cả a_i đều là số chính phương với mọi 1 <= i <= n.
• Subtask 3 (30% số điểm): a_i <= 1000 với mọi 1 <= i <= n.
• Subtask 4 (30% số điểm): Không có ràng buộc bổ sung.

Ví dụ 1:

Đầu vào:

5
2 8 3 12 50

Đầu ra:

4

Giải thích: Các cặp chỉ số (i, j) thỏa mãn là:

• (1, 2): a_1 = 2, a_2 = 8 -> LCM(2, 8) / GCD(2, 8) = 8 / 2 = 4 = 2^2.
• (1, 5): a_1 = 2, a_5 = 50 -> LCM(2, 50) / GCD(2, 50) = 50 / 2 = 25 = 5^2.
• (2, 5): a_2 = 8, a_5 = 50 -> LCM(8, 50) / GCD(8, 50) = 200 / 2 = 100 = 10^2.
• (3, 4): a_3 = 3, a_4 = 12 -> LCM(3, 12) / GCD(3, 12) = 12 / 3 = 4 = 2^2.