Đế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
Toán: Số học
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\) và \(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