Số Chữ Số 0 Liên Tiếp Cuối Cùng Của N! - Code 24h

Chúng ta sẽ bắt đầu với một bài toán nhỏ như sau:

Cho một số tự nhiên n, hãy tìm số chữ số 0 liên tiếp cuối cùng của n! (giai thừa)

Straight-forward

Một cách đơn giản và trực diện nhất, đó chính là brute-force, nhân tất vào, rồi đếm số chữ số 0

def trailing_zeros(n): if n == 0: return 0 product = 1 for i in range(2, n+1): product *= i tz = 0 while product%10 == 0: tz += 1 product /= 10 return tz

Đơn giản, dễ hiểu, nhưng rõ ràng là không hiệu quả về performance. Nếu bạn đã từng tham dự vào các cuộc thi Competitive Programming thì sẽ biết các cách giải kiểu brute-force này chắc chắn sẽ bị đánh giá là time-out!

Dùng cái đầu

Ta có nhận xét như sau: trailing_zeros(n) chính là số lần mà 10 xuất hiện trong khai triển n! n! n!

Tuy nhiên 10=2∗5 10 = 2*5 10=2∗5 , nên bài toán sẽ đưa về là tìm số lần xuất hiện của tích giữa 2 và 5 trong n! n! n! . Thêm nữa 5>2 5 > 2 5>2 , ta chắc chắn một điều là số lượng 5 xuất hiện ít hơn số lượng 2 xuất hiện, do đó cuối cùng ta chỉ cần đếm số lần 5 xuất hiện là đủ.

Đếm như thế nào ? Ta có thể nhẩm tính thế này: 5 xuất hiện trong 5, 10, 15, 20, 25, 30... nên tần suất của 5 sẽ là ⌊n5⌋ lfloorfrac{n}{5} floor ⌊5n​⌋ (ở đây là làm tròn xuống, tức floor).

Tuy nhiên như vậy là chưa đủ! Ta thấy 25 = 5*5, nghĩa là trong 25 xuất hiện 2 lần thừa số 5, tương tự với 50, 75, 100,... nghĩa là ta cần phải tính thêm một lần xuất hiện của 5 tại đây, tức ⌊n25⌋ lfloorfrac{n}{25} floor ⌊25n​⌋

Tương tự với 125, 625... ta đều phải tính thêm số lần 5 xuất hiện. Tổng quát lên, ta có công thức như sau:

f(n)=∑1k⌊n5i⌋=⌊n5⌋+⌊n52⌋+⌊n53⌋+...+⌊n5k⌋f(n) = sum_1^klfloorfrac{n}{5^i} floor = lfloorfrac{n}{5} floor + lfloorfrac{n}{5^2} floor + lfloorfrac{n}{5^{3}} floor + ... + lfloorfrac{n}{5^k} floor f(n)=1∑k​⌊5in​⌋=⌊5n​⌋+⌊52n​⌋+⌊53n​⌋+...+⌊5kn​⌋

Với 5k≤n<5k+1 5^{k} leq n <5^{k+1} 5k≤n<5k+1 , hay nói cách khác k=⌊log⁡5n⌋ k = lfloorlog_5{n} floor k=⌊log5​n⌋

Ví dụ: Tìm số lượng số chữ số 0 liên tiếp cuối cùng của 151!

• Vòng 1: ⌊1515⌋=30 lfloorfrac{151}{5} floor = 30 ⌊5151​⌋=30
• Vòng 2: ⌊15125⌋=6 lfloorfrac{151}{25} floor = 6 ⌊25151​⌋=6
• Vòng 3: ⌊151125⌋=1 lfloorfrac{151}{125} floor = 1 ⌊125151​⌋=1

Vậy có tất cả 30+6+1=37 30 + 6 + 1 = 37 30+6+1=37 số chữ số 0

Thuật toán ok rồi, code thôi: