用c++写折半查找求阶乘函数后K个零

这里给出一个用C++实现的求阶乘函数后K个零的折半查找算法。

#include <iostream>
using namespace std;

// 计算n的阶乘后有多少个0
int countZero(int n) {
    int count = 0;
    while (n > 0) {
        count += n / 5;
        n /= 5;
    }
    return count;
}

// 折半查找
int findK(int k) {
    int left = 0, right = 5 * k;
    while (left < right) {
        int mid = (left + right) / 2;
        if (countZero(mid) >= k) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

int main() {
    int k = 5;
    int res = findK(k);
    cout << "阶乘后" << k << "个零的位置为：" << res << endl;
    return 0;
}

这里的思路是先写一个计算n的阶乘后有多少个0的函数countZero，然后利用折半查找在0到5*k之间查找第一个满足countZero(mid)>=k的mid，最后返回mid即可。