8 Điểm Văn (Nằm Sân Trường)
Start of Real
3 năm cấp ba đối với Eme là quãng thời gian thật sự đáng nhớ đối với cậu. Cậu được phát triển bản thân về mọi mặt (ví dụ hai mặt, nấu xói, phá làng phá xóm, ...). Cậu cũng tạo ra những sự kiện kinh hoàng và đôi lúc lại nực cười với mọi người. Một trong những sự kiện đó là nguồn gốc của bức ảnh viral một thời.
Cậu từng rất tự ti về việc học Văn của bản thân. Cậu luôn có cảm giác dù mình có viết như thế nào thì cũng sẽ không được điểm cao. Tuy nhiên, cậu vẫn luôn cố gắng cải thiện. Trong đợt khảo sát cuối kì lần đó, cậu đã dùng hết những kiến thức được Mrs. Bông Mai truyền tải ở lớp để thả vào bài làm của mình. Cậu cược với nhóm của mình rằng nếu bản thân được trên 8 điểm, cậu sẽ ra nằm giữa sân trường.
Và thật may cho các bạn của cậu và không may (hoặc cũng không hẳn là không may) cho cậu, điểm Văn lần này được 8. Hậu quả là của cậu, cậu đành phải nằm ra giữa sân trường để trả kèo. Và tất nhiên, những chiếc điẹn thoại được giơ lên, chụp lại khoảnh khắc hiếm có này. Chiều hôm đó, sau một giấc ngủ trưa, cậu mở Facebook lên và tá hỏa khi thấy 1001 tài khoản đổi ảnh đại diện thành bức ảnh của cậu. Ngay đến Mrs. Bông Mai cũng đã thấy, và kể từ đó, bức ảnh huyền thoại đã liên tục được truyền lại cho đời sau.
End of Real
Để mọi người quên đi bức ảnh đó, cậu đã chế tạo ra một cỗ máy có khả năng xóa kí ức Deletememorinator. Cỗ máy hoạt động bằng cách thay đổi trạng thái nhớ/quên một kí ức của một người. Nếu máy bắn trúng một người đang nhớ kí ức, họ sẽ quên. Ngược lại, nếu người đó không biết, họ sẽ có kí ức đó. Cậu đánh số những người cần xóa kí ức từ 1 đến \(N\). Một khi nhấn nút, nó sẽ lặp lại công việc thay đổi cho người thứ nhất đến thứ \(N\). Cậu dự tính sẽ thay đổi một lần và mãi mãi. Tuy nhiên, trong khi xây dựng, cậu đã lắp nhầm một vài linh kiện, khiến cỗ máy trục trặc.
Nó đột nhiên yêu cầu Eme nhập một số nguyên \(k\) và chỉ chuyển thành thay đổi trạng thái nhớ/quên một kí ức của một người nếu mã số của người đó chia hết cho \(k\). Là một người thông minh, Eme chọn ngay \(k=1\). Tuy nhiên, Eme đã nhận ra mình lại lắp nhầm thêm một linh kiện khác. Nó khiến cỗ máy không chỉ lặp theo \(N\), nó còn lặp theo \(k\). Tức là với mỗi \(k\) chạy từ 1 đến \(N\), nó chạy một lần thay đổi kí ức.
Hãy giúp Eme biết số người đã bị xóa kí ức đó là bao nhiêu?
Dữ liệu
- Một dòng duy nhất chứa một số nguyên dương \(N \ (1\le N \le 10^{18})\).
Kết quả
- Kết quả bài toán.
Chấm điểm
- Subtask 1 (20%): \(N \le 10^3\).
- Subtask 2 (20%): \(N \le 10^6\).
- Subtask 3 (20%): \(N \le 10^{12}\).
- Subtask 4 (40%): Không có giới hạn gì thêm.
Ví dụ
Ví dụ 1
input
5
output
2
Giải thích
Dãy tình trạng kí ức của 5 người ban đầu là [Nhớ, Nhớ, Nhớ, Nhớ, Nhớ]
Ở lượt đầu tiên, máy thay đổi kí ức của những người có mã số chia hết cho 1: [Quên, Quên, Quên, Quên, Quên].
Ở lượt thứ hai, máy thay đổi kí ức của những người có mã số chia hết cho 2: [Quên, Nhớ, Quên, Nhớ, Quên].
Ở lượt thứ ba, máy thay đổi kí ức của những người có mã số chia hết cho 3: [Quên, Nhớ, Nhớ, Nhớ, Quên].
Ở lượt thứ tư, máy thay đổi kí ức của những người có mã số chia hết cho 4: [Quên, Nhớ, Nhớ, Quên, Quên].
Ở lượt thứ năm, máy thay đổi kí ức của những người có mã số chia hết cho 5: [Quên, Nhớ, Nhớ, Quên, Nhớ].
Comments