Chương trình đếm số chữ số 0 ở cuối của số nhỏ nhất chia hết cho 1 đến k trong Python

Cho số k, x là số nguyên dương nhỏ nhất chia hết cho mọi số từ 1 đến k (BCNN của 1..k). Tìm số chữ số 0 ở cuối của x.

Ví dụ: k = 6 → BCNN(1..6) = 60 → 1 chữ số 0.

Giải pháp

Số chữ số 0 ở cuối = số lần x chia hết cho 10 = min(số ước 2, số ước 5) trong phân tích thừa số nguyên tố của BCNN(1..k). Vì ước 2 luôn nhiều hơn ước 5, chỉ cần đếm số ước 5:

• res = 0, x = 1
• While x * 5 <= k: res++, x *= 5
• Trả về res

Ví dụ minh họa

class Solution:
    def solve(self, k):
        res = 0
        x = 1
        while x * 5 <= k:
            res += 1
            x *= 5
        return res

ob = Solution()
k = 6
print(ob.solve(k))

Đầu vào

6

Đầu ra

1