Hiểu bài toán

Bài toán yêu cầu đếm số lượng số 0 liên tiếp tính từ hàng đơn vị (phía bên phải) của kết quả n! (n giai thừa). Đây chính là đếm số lượng thừa số 25 trong phân tích thừa số nguyên tố của n! (vì mỗi cặp 25 tạo thành một số 0). Tuy nhiên, trong n! luôn có nhiều thừa số 2 hơn thừa số 5, nên số lượng số 0 ở cuối phụ thuộc hoàn vào số lượng thừa số 5 trong n!. Do đó, bài toán quy về việc tính tổng số lượng thừa số 5 trong các số từ 1 đến n.

Các cách tiếp cận

Cách Tính trực tiếp bằng đệ quy (Có thể sai/như Solution 3)

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll luythua(ll a,ll b)
{
  if(b==0) return 1;
  if(b==1) return a;
  ll x=luythua(a,b/2);
  if(b%2==0) return x*x;
  return x*x*a;
}
int main() 
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    ll n;
    cin>>n;
    ll s=0;
    for(int i=1;i<=n;i++){
      if(luythua(5,i)<=n) s+=n/(luythua(5,i));
    }
    cout<<s;
}

• Time Complexity: O(log n)
• Space Complexity: O(log n)

Approach này dựa trên công thức Legendre: tổng số lượng thừa số 5 trong n! là tổng của floor(n/5) + floor(n/25) + ... Code thực hiện vòng lặp với biến i tăng dần, tính 5^i (dùng hàm luythua) và cộng dồn n/(5^i) vào kết quả. Tuy nhiên, cách đặt tên biến và vòng lặp có thể gây hiểu nhầm nếu không đọc kỹ công thức Legendre. Logic tính toán là đúng (nếu độ dài số cho phép).

Cách Vòng lặp chia 5 (Phiên bản 1)

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int count = 0;
    while (n >= 5) {
        count += n / 5;
        n /= 5;
    }
    cout << count << endl;
    return 0;
}

• Time Complexity: O(log n)
• Space Complexity: O(1)

Đây là cách biến thể của công thức Legendre. Thay vì tính lũy thừa 5, ta chia不断 n cho 5. Vòng lặp while (n >= 5) thực hiện: count += n/5 (đếm các số chia hết cho 5), sau đó n = n/5 (để đếm các số chia hết cho 25, 125... ở các bước tiếp theo). Đây là thuật toán chuẩn để giải bài toán đếm số 0 giai thừa.

Cách Vòng lặp lũy thừa 5 (Phiên bản 2)

#include<bits/stdc++.h>
#define ll long long
using namespace std;

ll n;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n;
    ll ans = 0, s = 5;
    for (int i = 1; s <= n; ++i){
        ans += n/s;
        s *= 5;
    }
    cout << ans;
    return 0;
}

• Time Complexity: O(log n)
• Space Complexity: O(1)

Cách tiếp cận này dùng biến s để lưu lũy thừa của 5 (bắt đầu bằng 5). Vòng lặp for chạy chừng nào s còn nhỏ hơn hoặc bằng n. Trong mỗi bước, nó cộng n/s vào kết quả và nhân s lên 5 lần. Đây là cách cài đặt trực tiếp nhất của công thức Legendre: count = n/5 + n/25 + n/125 + ...

Phân tích độ phức tạp

Bài học kinh nghiệm

• Số lượng số 0 ở cuối n! bằng số lượng cặp thừa số (2, 5) trong phân tích thừa số nguyên tố.
• Trong n!, số lượng thừa số 2 luôn nhiều hơn số lượng thừa số 5, nên số lượng số 0 bằng số lượng thừa số 5.
• Công thức tính số lượng thừa số 5 là tổng: floor(n/5) + floor(n/25) + floor(n/125) + ...

Lỗi thường gặp

• Không nên tính trực tiếp giá trị n! vì kích thước số quá lớn (n <= 1000) gây tràn số (overflow).
• Sai lầm khi đếm số lượng số chia hết cho 10 thay vì đếm thừa số 5 (ví dụ: 25 có 2 thừa số 5 nhưng chỉ chia hết cho 10 một lần).