Đếm ước chung lớn nhất
Point: 100.0
Time limit: 1.0s
Memory limit: 64 M
Input: stdin
Output: stdout
Author:  
Problem type
Ngôn ngữ cho phép
C, C#, C++, Java, Pascal, Python, Text

Yêu cầu:

Cho dãy số nguyên \((a_1, a_2,..., a_n)\), hãy đếm số cặp \((i, j)\) thỏa mãn: \(1 ≤ i < j ≤ n\)\(gcd(a_i, a_j ) > 1\)

gcd là phép lấy ước chung lớn nhất của hai số.

Dữ liệu:

  • Dòng đầu tiên ghi số nguyên không âm \(n (0 < n ≤ 100)\),

  • Dòng thứ 2 ghi \(n\) số nguyên dương kiểu 64 – bit.

Kết quả:

  • In ra số lượng cặp \((i, j)\) thỏa mãn yêu cầu.

Dữ liệu vào

3
21 6 57

Output

3