题目描述

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，找出多少个非负整数 x，能满足 f(x) = K 。

样例

long long int pow1(int x, int y)
{
    long long int k = x;
    while(y>1)
    {
        y--;
        k*=x;
    }
    return k;
}
int preimageSizeFZF(int K){
    int test=K,layer=1;
    while(true)
    {
        if((pow1(5,layer+1)-1)/4>K)
            break;
        layer++;
    }
    while(layer>1)
    {
        test-= test/((pow1(5,layer)-1)/4);
        layer --;
    }
    K -= test;
    int i = test/5;
    for(layer=1;i>0;layer++,i/=5)
    {
        K -=test/pow1(5,layer);
    }
    if(K==0)return 5;
    else return 0;
}

算法1

(数学)

由于答案有两种情况，先假设是其中一种情况，把0的个数做为切入点，不考虑具体x，而是看小于x的5的倍数的个数，根据假设，这是可求的，求出后据此求0的个数，若相吻合则假设成立

时间复杂度

O(logk)