DS查找—折半查找求阶乘函数后K个零

DS查找—折半查找求阶乘函数后K个零

题目描述

f(x) 是 x! 末尾是 0 的数量，给定 K，找出多少个非负整数 x ，能满足 f(x) = K 。
（x! = 1 * 2 * 3 * … * x，且 0! = 1 ） 例如， f(3) = 0 ，因为 3! = 6 的末尾没有 0 ；
而 f(11) = 2 ，因为 11!= 39916800 末端有 2 个 0 。

提示：
函数 f的表达式：从表达式中可以看出，f(x) 有多个取整函数相加组成，取整函数是阶梯状变化的， 所以 f(x) 也一定是阶梯状的。接下来观察阶梯的上升位置，和式的第 i项的阶梯上升点为 , 也就是 的倍数，由于的倍数都是 5 的倍数，所以阶梯的上升点都在 5 的倍数的位置， 于是可以得到：所有阶梯的长度相等，都为 5。从方程 f(x)=K 的角度，可以得到下面这个结论： 如果方程 f(x)=K 有正整数解，则解的数量必定为 5 所以问题转化为了方程 f(x)=K是否有解。 由于 f(x)是递增函数，是单调的，所以可以尝试使用二分查找法。 这里又有初始上下界选取的问题，为了查找次数少，需要尽可能压缩范围。

首先，注意到：
于是可得：
所以下界为4K
又有：
所以上界为 5K5K。
之后套用二分查找的算法即可。
4K4K。

输入

第一行输入测试数据组数t；
接下来输入t组测试数据K，测试数据K的取值范围为[0, 10^9] 的整数。

输出

输出每组测试数据对应的x个数。

样例输入

3 0 5 3

样例输出

5 0 5

提示

1、阶乘末尾0的个数与阶乘可以分离“质因数5”的个数相等
2、阶乘函数X！末尾有K个零，这样的X可能有五个，可能没有

#include ;
using namespace std;

void preimageSizeFZF(int K)
{
    //确定阶梯值范围 最终的到的K < start
    int start = 1;
    while (start < K)
    {
        start = start * 5 + 1;
    }
    //确定范围后，执行精确查找
    while (start > 1)
    {
        //只有5以下阶乘才会出现start-1成立，其它情况不会存在，因为任何一个阶段分界值都会包含一个以上的5
        if (start - 1 == K)
        {
            //不存在的返回0
            cout << 0 << endl;
        }
        //逆推下一个阶梯值 从f(x+1) 推导出f(x)
        start = (start - 1) / 5;
        //获取剩余值，进行下一阶梯运算
        K %= start;
    }
    //只要存在，必然是5个
    cout << 5 << endl;
}

int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        preimageSizeFZF(n);
    }
    return 0;
}