Chương trình tìm số m nhỏ nhất có n số 0 ở cuối giai thừa trong Python

Cho n, tìm m nhỏ nhất sao cho m! có ít nhất n số 0 tận cùng. Số 0 tận cùng của giai thừa bằng số ước 5 (vì 2 dư thừa).

Thuật toán

• Hàm count_fives(n) đếm số ước 5 trong n! (chia liên tiếp cho 5).
• Tìm kiếm nhị phân trên khoảng [1, 5^24] để tìm m nhỏ nhất có count_fives(m) ≥ n.
• Khi tìm thấy fives == n, thu hẹp khoảng về [mid-5, mid].

Ví dụ

def count_fives(n):
    cnt = 0
    while n > 0:
        n //= 5
        cnt += n
    return cnt

def solve(n):
    left, right = 1, 5**24
    while right - left > 5:
        mid = int((right + left) / 10) * 5
        fives = count_fives(mid)
        if fives == n:
            right = mid
            left = right - 5
            break
        elif fives < n:
            left = mid
        else:
            right = mid
    return right

print(solve(2))  # Output: 10

Giải thích

10! = 3628800 (2 số 0), 9! = 362880 (1 số 0) → m=10.