Hiểu bài toán

Cho một số nguyên dương N, tìm số nguyên dương M nhỏ nhất sao cho số giai thừa M! có đúng N chữ số 0 ở cuối. Dữ liệu input bao gồm T truy vấn, mỗi truy vấn cho một số N (1 ≤ N ≤ 10^16). Ta cần tìm M tương ứng cho mỗi N.

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

Cách Tìm kiếm nhị phân (Binary Search) - Phân tích xu hướng

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

typedef long long ll;

// Hàm đếm số chữ số 0 ở cuối của n!
ll countZeros(ll n) {
    ll count = 0;
    while (n >= 5) {
        n /= 5;
        count += n;
    }
    return count;
}

void solve() {
    ll n;
    cin >> n;
    // Tìm kiếm nhị phân cho M
    // Biên dưới: 1, Biên trên: đủ lớn (ví dụ 5 * N)
    ll l = 1, r = 5 * n; 
    ll ans = -1;
    while (l <= r) {
        ll mid = l + (r - l) / 2;
        if (countZeros(mid) >= n) {
            ans = mid;
            r = mid - 1; // Thử tìm giá trị nhỏ hơn
        } else {
            l = mid + 1;
        }
    }
    cout << ans << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

• Time Complexity: O(log(N) * log(N)) ~ O(log^2 N) mỗi truy vấn
• Space Complexity: O(1)

Số lượng số 0 ở cuối M! được tính bằng tổng số bội của 5 trong các số từ 1 đến M (do số 2 luôn dồi dào hơn 5). Hàm countZeros(M) tính giá trị này bằng cách chia lũy thừa cho 5. Hàm này là đơn điệu tăng (non-decreasing). Do đó, ta có thể áp dụng tìm kiếm nhị phân để tìm giá trị M nhỏ nhất sao cho countZeros(M) >= N. Với N lên tới 10^16, giá trị M tìm kiếm nằm trong khoảng [1, 5 * N] (thực tế nhỏ hơn nhiều).

Cách Tìm kiếm nhị phân (Cải tiến)

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

typedef long long ll;

ll cal(ll n) {
    ll res = 0;
    while (n) {
        res += (n / 5);
        n /= 5;
    }
    return res;
}

void solve() {
    ll n;
    cin >> n;
    ll l = 1, r = 2e18; // Sử dụng biên trên an toàn
    ll ans = 0;
    while (l <= r) {
        ll md = l + (r - l) / 2;
        if (cal(md) >= n) {
            ans = md;
            r = md - 1;
        } else {
            l = md + 1;
        }
    }
    cout << ans << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int tt;
    cin >> tt;
    while (tt--) solve();
}

• Time Complexity: O(log(MaxM) * log(MaxM))
• Space Complexity: O(1)

Cách tiếp cận tương tự như giải pháp 1, nhưng sử dụng biên trên lớn hơn (2e18) để đảm bảo bao quát mọi trường hợp. Logic tìm kiếm nhị phân giữ nguyên: tìm giá trị nhỏ nhất sao cho hàm đếm số 0 (cal) trả về kết quả >= N.

Cách Tìm kiếm nhị phân (Biến thể)

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

#define int long long

int q;
int n;

int cnt(int s) {
    int d = 0;
    while (s >= 5) {
        s /= 5;
        d += s;
    }
    return d;
}

main() {
    cin >> q;
    while (q--) {
        cin >> n;
        int l = 1, r = 1e18, ans = 0;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (cnt(mid) < n) {
                ans = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        cout << ans + 1 << '\n';
    }
}

• Time Complexity: O(log(MaxM) * log(MaxM))
• Space Complexity: O(1)

Biến thể này tìm kiếm giá trị M lớn nhất sao cho cnt(M) < N. Vì hàm cnt(M) là đơn điệu tăng, giá trị M lớn nhất thỏa mãn cnt(M) < N chính là giá trị M nhỏ nhất thỏa mãn cnt(M) >= N trừ đi 1. Tuy nhiên, trong code tác giả in ra ans + 1. Logic này đúng: 'ans' lưu giá trị cuối cùng mà cnt(ans) < N, do đó ans + 1 là số đầu tiên mà cnt(ans + 1) >= N. Đây là cách viết khác của cùng một thuật toán.

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

Bài học kinh nghiệm

• Số lượng số 0 ở cuối M! bằng tổng số bội của 5 trong các số từ 1 đến M.
• Hàm đếm số 0 là đơn điệu tăng, cho phép áp dụng tìm kiếm nhị phân để tìm M tối ưu.
• Với N <= 10^16, giá trị M trả về sẽ không vượt quá 5 * N (thực tế khoảng 8e16), nhưng biên trên 10^18 hoặc 2e18 là an toàn.

Lỗi thường gặp

• Sử dụng kiểu dữ liệu int (32-bit) thay vì long long (64-bit) có thể gây tràn số do N và M rất lớn.
• Việc chọn biên trên (upper bound) quá nhỏ trong tìm kiếm nhị phân có thể bỏ lỡ kết quả chính xác.
• Lỗi logic trong việc tính toán số 0 (ví dụ: đếm số chia hết cho 10 thay vì chia hết cho 5).