Kích thước tiền ảnh hàm số 0 cuối giai thừa (Preimage Size of Factorial Zeroes Function) trong C++

Hàm f(x) = số chữ số 0 cuối của x!. Cho K, tìm số nguyên không âm x thỏa f(x) = K.

Ví dụ

K = 2 → kết quả 5 (các x: 10,11,12,13,14).

Thuật toán

1. Hàm ok(x) đếm số 0 cuối của x! bằng công thức Legendre: x/5 + x/25 + x/125 + ...
2. Nhận thấy f(x) là hàm không giảm, mỗi giá trị K xuất hiện 0 hoặc 5 lần.
3. Dùng tìm kiếm nhị phân tìm x nhỏ nhất sao cho f(x) ≥ K.
4. Nếu f(x) == K trả về 5, ngược lại 0.

Chương trình C++

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

class Solution {
    lli ok(lli x) {
        lli ret = 0;
        for(lli i=5; i<=x; i*=5) ret += x/i;
        return ret;
    }
public:
    int preimageSizeFZF(int K) {
        if(K == 0) return 5;
        lli low = 1, high = (lli)K * 5;
        while(low < high) {
            lli mid = low + (high - low)/2;
            if(ok(mid) < K) low = mid + 1;
            else high = mid;
        }
        return ok(low) == K ? 5 : 0;
    }
};

int main() {
    Solution ob;
    cout << ob.preimageSizeFZF(2); // 5
    return 0;
}