Nội dung bài toán

Cho một danh sách gồm ~ n ~ số nguyên dương, nhiệm vụ của bạn là đếm số cặp số ~(a, b)~ trong danh sách sao cho hai số này nguyên tố cùng nhau (tức là ~\text{gcd}(a, b) = 1~).

Dữ liệu vào

• Dòng đầu tiên chứa một số nguyên ~ n ~: số lượng phần tử trong danh sách.
• Dòng thứ hai chứa ~ n ~ số nguyên ~ x_1, x_2, \ldots, x_n ~: các phần tử của danh sách.

Dữ liệu ra

• In ra một số nguyên: số lượng cặp ~(a, b)~ sao cho ~\text{gcd}(a, b) = 1~.

Ràng buộc

• ~ 1 \leq n \leq 10^5 ~
• ~ 1 \leq x_i \leq 10^6 ~

Ví dụ

Dữ liệu vào

8
5 4 20 1 16 17 5 15

Dữ liệu ra

19

Giải thích:

• Tổng cộng có ~ \binom{8}{2} = 28 ~ cặp số.
• Trong đó, có 19 cặp số thỏa mãn ~\text{gcd}(a, b) = 1~.