C++二分查找算法：阶乘函数后 K 个零

class Solution {
public:
int preimageSizeFZF(int k) {
return FirstEqualMore(k + 1) - FirstEqualMore(k);
}
int FirstEqualMore(int k)
{
long long left = -1, right = k * 5LL;
while (right - left > 1)
{
const auto mid = left + (right - left) / 2;
if (GetNum(mid) >= k)
{
right = mid;
}
else
{
left = mid;
}
}
return right;
}
long long GetNum(long long llVaue)
{
long long llRet = 0;
long long five = 5;
while (five <= llVaue)
{
llRet += llVaue / five;
five *= 5;
}
return llRet;
}
};

template
void Assert(const T& t1, const T& t2)
{
assert(t1 == t2);
}
template
void Assert(const vector& v1, const vector& v2)
{
if (v1.size() != v2.size())
{
assert(false);
return;
}
for (int i = 0; i < v1.size(); i++)
{
Assert(v1[i], v2[i]);
}
}
int main()
{
vector<vector> grid;
int res = 0;
{
Solution slu;
res = slu.preimageSizeFZF(0);
Assert(5, res);
}
{
Solution slu;
res = slu.preimageSizeFZF(5);
Assert(0, res);
}
{
Solution slu;
res = slu.preimageSizeFZF(3);
Assert(5, res);
}

class Solution {
public:
int preimageSizeFZF(int k) {
int left = 0, right = 1000 * 1000 * 1000 + 1;
while (right > left + 1)
{
int iMid = left + (right - left) / 2;
const int iNum = GetFiveNum(iMid);
if (iNum == k)
{
return 5;
}
else if (iNum < k)
{
left = iMid;
}
else
{
right = iMid;
}
}
return (GetFiveNum(left) == k) ? 5 : 0;
}
//获取[0,iMax*5] 质因数5的个数
int GetFiveNum(int iMax)
{
int iNum = iMax;
int tmp = 5;
while (iMax >= tmp)
{
iNum += iMax / tmp;
tmp *= 5;
}
return iNum;
}
};