Số họcChia hết
Mô tả
ZaloPay đang chạy chương trình khuyến mãi độc đáo dành cho người dùng quen thuộc với toán học. Cụ thể, nếu bạn là người dùng có mã số là N, thì số điểm thưởng bạn nhận được sẽ bằng chính giá trị của N giai thừa (ký hiệu là N!). Để quảng cáo rầm rộ, đội ngũ truyền thông quyết định sẽ lấy đúng số lượng các chữ số 0 tận cùng của điểm thưởng làm phần quà tặng kèm ví như voucher, thẻ cào.
Nhiệm vụ của bạn là: cho trước một mã số người dùng N, hãy tính toán xem N! có bao nhiêu chữ số 0 tận cùng để đội ngũ truyền thông chuẩn bị đúng số lượng phần quà.
Đầu vào
- Một số nguyên dương N (1 ≤ N ≤ 10^9).
Đầu ra
- In ra một số nguyên duy nhất là số lượng chữ số 0 tận cùng của N!.
Ràng buộc
- 1 ≤ N ≤ 10^9.
- Bài toán yêu cầu độ phức tạp thời gian O(log N). Không được phép tính trực tiếp giá trị của N! vì sẽ gây tràn số ngay cả với kiểu dữ liệu 64-bit khi N ≥ 21.
Ví dụ
Ví dụ 1:
- Đầu vào:
10 - Đầu ra:
2 - Giải thích: Mã số người dùng là 10. Ta có 10! = 3628800. Số này có 2 chữ số 0 tận cùng, nên đội ngũ truyền thông sẽ chuẩn bị 2 phần quà tặng kèm.
Ví dụ 2:
- Đầu vào:
25 - Đầu ra:
6 - Giải thích: 25! có 6 chữ số 0 tận cùng. Lý do là ngoài các bội của 5 thông thường như 5, 10, 15, 20 (mỗi số đóng góp một thừa số 5), số 25 đóng góp tới hai thừa số 5 vì 25 = 5^2. Tổng cộng có 6 thừa số 5, và cũng có hơn 6 thừa số 2, tạo ra 6 cặp (2, 5) tức 6 chữ số 0.