Phân số tối giản
Xem dạng PDF
Gửi bài giải
Điểm:
10,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
Ngôn ngữ cho phép
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch
Phân số được gọi là phân số tối giản nếu ước chung lớn nhất của tử số và mẫu số bằng 1.
Yêu cầu: Cho trước một số nguyên dương ~N~. Hãy đếm xem có bao nhiêu phân số dương bé hơn 1, có mẫu là ~N~ và là phân số tối giản.
Dữ liệu vào:
- Gồm một số nguyên dương ~N~ (~N ≤ 10^{16}~).
Dữ liệu ra:
- Gốm 1 số nguyên ~M~ là số lượng phân số theo yêu cầu trên.
Ví dụ:
Input
9
Output
6
Ràng buộc:
- Subtask1: 30% test với ~N≤10^6~.
- Subtask2: 40% test với ~10^6 ≤ N ≤ 10^9~.
- Subtask3: 30% test còn lại không có ràng buộc gì thêm.
Bình luận
thấy tk ở trên gay thì bấm ^
nói rằng mình là người thanh hoá
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
~x^~~x^~