阶乘后K个零

思路: 首先X阶乘后0的个数等于1-x 中包含2,5质因子的个数.  其中2的质因子个数小于5的个数,  所以 求0的个数就等于求出质因子5的个数

设f(x) 为 x阶乘后0的个数, 则 f(x) = x/5 + x/5^2 + ...+ x/5^k  (此处必然存在一个k 使得 x < 5^k)  且 f(x) 单调不减

本题目是求阶乘后k个0的数的个数   由于f(x)单调不减的特性, 我们可以用二分求出阶乘后不大于k个0的最大x

则阶乘后k个0的数的个数  就等于阶乘后不大于k个0的最大x - 阶乘后不大于k-1个0的最大x

class Solution {
public:
    typedef long long LL;
    LL Ans(LL n)
    {
        LL l = -1;
        LL r = 1e18;
        while(l < r)
        {
            LL mid = (l+r+1)>>1;
            LL ans = 0;
            LL tmp = mid;
            while(tmp)
            {
                ans += tmp/5;
                tmp /= 5;
            }
            if(ans<=n)l = mid;
            else r = mid - 1;
        }
        return l;
    }
    int preimageSizeFZF(int k) {
        return (Ans(k) - Ans(k-1));
    }
};