思路: 首先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)); } };