172.阶乘后的零 | 793.阶乘函数后k个零

172.阶乘后的零

给定一个整数 n ，返回 n! 结果中尾随零的数量。

提示 n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1

示例 1：

输入：n = 3
输出：0
解释：3! = 6 ，不含尾随 0
示例 2：

输入：n = 5
输出：1
解释：5! = 120 ，有一个尾随 0

 思路：

n！中尾随0的数量 = n！可以分解出因子5的个数

因为有因子2和因子5，2X5=10，就可以提供一个0，而n！中只要是偶数就至少可以提供一个因子2，即因子2比因子5多的多，所以n！中的因子5的个数就等于n！中尾随0的个数（拿到一个因子5就可以和因子2凑出一个尾随0）。

class Solution {
public:
    //n！的结果中尾随0的数量 = n！可以分解出因子5的个数
    //例子：125！=125*124*123*...*2*1
    /*
    125/5=25，5的倍数肯定可以提供一个因子5，如：5，10，15，20，25...
    125/25=5，25的倍数肯定可以提供两个因子5，如：25，50，75，100，125
    125/125=1，125的倍数肯定可以提供三个因子5，如：125
    所以125！共可以提供25+5+1=31个因子5，也就有31个尾随0。
    */
    int trailingZeroes(int n) {
        int res=0;
        int dis=5;
        while(dis<=n)
        {
            res+=n/dis;
            dis*=5;
        }
        return res;    
    }
};

793.阶乘函数后k个零

 f(x) 是 x! 末尾是 0 的数量。回想一下 x! = 1 * 2 * 3 * ... * x，且 0! = 1 。

例如， f(3) = 0 ，因为 3! = 6 的末尾没有 0 ；而 f(11) = 2 ，因为 11!= 39916800 末端有 2 个 0 。
给定 k，找出返回能满足 f(x) = k 的非负整数 x 的数量。

示例 1：

输入：k = 0
输出：5
解释：0!, 1!, 2!, 3!, 和 4! 均符合 k = 0 的条件。
示例 2：

输入：k = 5
输出：0
解释：没有匹配到这样的 x!，符合 k = 5 的条件。

思路：二分搜索

要求有多少个数满足阶乘后的0的个数等于k，就是在求满足条件的数中，最小的数是多少，最大的数是多少，最大值最小值一减，差就是结果。

因为在穷举 n = 1 ~ LONG_MAX 的过程中，随着 n 的增加，n! 肯定是递增的，阶乘后的0的个数肯定也是递增的，所以可以利用二分查找，找到符合条件的数的最小值（搜索左侧边界），找到符合条件的数的最大值（搜索右侧边界）。

class Solution {
public:
    long countZero(long n)//返回n！后的0的个数
    {
        long res=0;
        long dis=5;
        while(dis<=n)
        {
            res+=n/dis;
            dis*=5;
        }
        return res;
    }
 
    int preimageSizeFZF(int k) 
    {
       return rightBound(k)-leftBound(k)+1;
    }
 
    long rightBound(int k)//搜索右侧边界
    {
        long low=0;
        long high=LONG_MAX;
        while(low//左闭右开区间
        {
            long mid=low+(high-low)/2;
            if(countZero(mid)>k)
            {
                high=mid;
            }
            else if(countZero(mid)
            {
                low=mid+1;
            }
            else//找到了符合条件的数，但是不返回，依然向右逼近
            {
                low=mid+1;
            }
        }
        return low-1;
    }
 
    long leftBound(int k)//搜索左侧边界
    {
        long low=0;
        long high=LONG_MAX;
        while(low//左闭右开区间
        {
            long mid=low+(high-low)/2;
            if(countZero(mid)
            {
                low=mid+1;
            }
            else if(countZero(mid)>k)
            {
                high=mid;
            }
            else//找到符合条件的数，但是不返回，依然向左逼近
            {
                high=mid;
            }
        }
        return low;
    }
};