Chương trình C++ tìm số X nhỏ nhất sao cho X! chứa ít nhất Y số 0 tận cùng

Cho số Y, tìm số X nhỏ nhất sao cho X! chứa ít nhất Y số 0 tận cùng. Ví dụ Y = 2 thì X = 10 vì 10! = 3628800 có 2 số 0 tận cùng.

Giải bằng tìm kiếm nhị phân. Số chữ số 0 tận cùng trong N! bằng số ước số 5 trong N!. X tìm được bằng tìm kiếm nhị phân trong khoảng [0, 5*Y].

Ví dụ mã nguồn

#include <iostream>
using namespace std;

int factorCount(int n, int X) {
    if (X < n)
        return 0;
    return (X / n + factorCount(n, X / n));
}

int findX(int Y) {
    int left = 0, right = 5 * Y;
    int N = 0;
    while (left <= right) {
        int mid = (right + left) / 2;
        if (factorCount(5, mid) < Y) {
            left = mid + 1;
        } else {
            N = mid;
            right = mid - 1;
        }
    }
    return N;
}

int main() {
    int Y = 4;
    cout << "Smallest value of X: " << findX(Y);
}

Kết quả đầu ra

Smallest value of X: 20