LeetCode C++ 判断n的阶乘后有多少个0,以及满足阶乘后K个0的数的个数
long trailingZeroes(long n) //判断n!结果末尾有多少个0
{
long res = 0;
for (long d = n; d / 5 > 0; d = d / 5) {
res += d / 5;
}
return res;
}
long leftBound(long target)
{
long low = 0;
long high = LONG_MAX - 1;
while (low <= high)
{
long mid = low + (high - low) / 2;
long temp = trailingZeroes(mid);
if (temp > target)
{
high = mid - 1;
}
else if (temp == target)
{
high = mid - 1;
}
else
{
low = mid + 1;
}
}
return low;
}
long rightBound(long target)
{
long low = 0;
long high = LONG_MAX - 1;
while (low <= high)
{
long mid = low + (high - low) / 2;
long temp = trailingZeroes(mid);
if (temp > target)
{
high = mid - 1;
}
else if (temp == target)
{
low = mid + 1;
}
else
{
low = mid + 1;
}
}
return high;
}
int preimageSizeFZF(int K) // 满足阶乘后K个0结尾的数的个数
{
long r = rightBound(K);
long l = leftBound(K);
return r - l + 1;
}