Cặp số nguyên tố cùng nhau trong đoạn
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Dạng bài
Cho số nguyên N. Hãy đếm số lượng cặp (i, j) sao cho 1 <= i < j <= N và GCD(i, j) = 1.
Dữ liệu vào:
Dòng 1: N (1 <= N <= 10^6).
Dữ liệu ra:
Số lượng cặp.
Ví dụ:
Input:
4
Output:
5
Các cặp đúng là (1,2), (1,3), (1,4), (2,3), (3,4).
Bình luận