// 0793. Preimage Size of Factorial Zeroes Function
class Solution {
public int preimageSizeFZF(int k) {
long left = 0;
long right = k * 5L;
long middle;
while (left < right) {
middle = (left + right) / 2;
int zeroes = trailingZeroes(middle);
if (zeroes > k) {
right = middle - 1;
} else if (zeroes < k) {
left = middle + 1;
} else {
left = middle;
right = middle;
}
}
if (trailingZeroes(left) == k) return 5;
return 0;
}
private int trailingZeroes(long n) {
int ans = 0;
while (n != 0) {
n /= 5;
ans += n;
}
return ans;
}
}
学习笔记：
这道题用到了很多数学的内容，还有二分法内容。
这道题的基础先是0172. Factorial Trailing Zeroes这道中等题。
2因素肯定比5多，所以最后几个0得看有几个5参与运算了。
5,10,15,20这都还是1个5参与，但25,50,75,100可就有2个5了，125,250,375,500那就有3个5了。规律其实就是把那个数字除以5看一下还剩多少，加上去，再除以5看一下剩多少，一直除到0为止。
比如130的阶乘，
先除以5得26，答案先是26，代表有26个单个5参与了。（5,10,15,20……）
再除以5得5，答案先是31，代表有5个双个5参与了。（25,50,75,100,125）
再除以5得1，答案是32，代表有1个三个5参与了。（125）
就是这样层层计算可以得出130阶层最后有32个5参与运算，也就有32个零在最后。
接下来，回到本题！
我们要用二分法处理这道题目，left是0，这个很好理解，right是多少呢？直接写2147482647会超时的，所以得有合适的范围。
我们知道：
要有一个5参与运算，至少是5的阶乘，
要有两个5参与运算，至少是10的阶乘，
要有五个5参与运算，至少是25的阶乘，
但是要有六个5参与运算，还是至少是25的阶乘，因为25里有两个5。
要有十二个5参与运算，至少是50的阶乘。
所以这个至少几的阶乘，一定是会小于5的数量的五倍的。
这一点我很难想通，但是现在起码想通了，如果再想不通得看上面这段例举了。
因此右边界就确定是k*5了，但这道题最后一个样例坑爹了是1000000000，乘完会越界然后结果就不对了，这个得需要用到long。
我在二分法求出结果后做的校验方案就是如果那这个left去求解，刚好是k，那么说明存在，也就是会有5个数字，可能是01234结尾也可能是56789结尾。
但如果不等于k，那说明不存在，也就是一下子阶乘计算中乘了一个带有多个5的数字。
真是一道特别绕的题目，虽然只是小学数学，但数学思路不太好的笨蛋绕到死也会解不开的吧。
